Home
How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?
Tags:, , , ,

How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?

September 2, 2019 No Comments algorithms, c / c++, DFS, recursive

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Recursive Approach – Divide and Conquer

The last element of the postorder is the root element, and since all the elements are unique, we can search for root in the inorder sequence. Then, all elements up to the root are grouped as left tree – which we can recursively solve. All elements from the root till the end in the inorder sequence are in the right tree – which can be recursively solved as well.

Given the root position in the inorder sequence, we can divide the post-order sequence by left and right tree as well. The overall approach would thus be recursively divide-and-conquer to construct the left and right tree, usin the Depth First Search Algorithm.

However, since copying to sub-array takes O(N) complexity, the following self-contained implementation takes O(N^2) overall.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if ((postorder.empty()) || (inorder.empty())) {
            return NULL;
        }
        TreeNode* root = new TreeNode(postorder.back());
        int i = 0;
        while ((i < inorder.size()) && (inorder[i] != root->val)) i ++;
        if (i == inorder.size()) {
            return root;
        }
        vector<int> left1(begin(inorder), begin(inorder) + i);
        vector<int> right1(begin(postorder), begin(postorder) + i);
        vector<int> left2(begin(inorder) + i + 1, end(inorder));
        vector<int> right2(begin(postorder) + i, end(postorder) - 1);
        if (i > 0) {
            root->left = buildTree(left1, right1);
        }
        if (i < inorder.size()) {
            root->right = buildTree(left2, right2);
        }
        return root;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if ((postorder.empty()) || (inorder.empty())) {
            return NULL;
        }
        TreeNode* root = new TreeNode(postorder.back());
        int i = 0;
        while ((i < inorder.size()) && (inorder[i] != root->val)) i ++;
        if (i == inorder.size()) {
            return root;
        }
        vector<int> left1(begin(inorder), begin(inorder) + i);
        vector<int> right1(begin(postorder), begin(postorder) + i);
        vector<int> left2(begin(inorder) + i + 1, end(inorder));
        vector<int> right2(begin(postorder) + i, end(postorder) - 1);
        if (i > 0) {
            root->left = buildTree(left1, right1);
        }
        if (i < inorder.size()) {
            root->right = buildTree(left2, right2);
        }
        return root;
    }
};

The above C++ implementation has overheads of copying (slicing) the sub arrays – then recursively call itself to construct the binary tree from the inorder and postorder sequences. We can slightly improve the memory/time efficiency by using the indices to represent the ranges of the sub-trees.

The helper function specifies the two sets of the ranges, and the algorithm complexity is the O(N) because there is no need to copy over the sub-arrays but using the indices.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
private:
    TreeNode* helper(vector<int>& inorder, int a, int b, vector<int>& postorder, int c, int d) {
        if ((a > b) || (c > d)) return NULL;
        TreeNode* root = new TreeNode(postorder[d]);
        int i = a;
        while ((i <= b) && (inorder[i] != root->val)) i ++;
        if (i > b) {
            return root;
        }
        int mid = c + i - a - 1;
        root->left = helper(inorder, a, i - 1, postorder, c, mid);
        root->right = helper(inorder, i + 1, b, postorder, mid + 1, d - 1);
        return root;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
private:
    TreeNode* helper(vector<int>& inorder, int a, int b, vector<int>& postorder, int c, int d) {
        if ((a > b) || (c > d)) return NULL;
        TreeNode* root = new TreeNode(postorder[d]);
        int i = a;
        while ((i <= b) && (inorder[i] != root->val)) i ++;
        if (i > b) {
            return root;
        }
        int mid = c + i - a - 1;
        root->left = helper(inorder, a, i - 1, postorder, c, mid);
        root->right = helper(inorder, i + 1, b, postorder, mid + 1, d - 1);
        return root;
    }
};

You can use the same divide-and-conquer algorithm to solve this as well: Algorithm to Construct Binary Tree from Preorder and Inorder Traversal

Related Binary Tree Construction Algorithms

You may also like the following posts on the similar tree problems.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
942 words
Last Post: How to Flatten 2D Vector in C++?
Next Post: How to Construct the Maximum Binary Tree using Divide-and-Conquer Recursion Algorithm?

The Permanent URL is: How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?

Related posts:

  1. The 24 Game Algorithm using Depth First Search You have 4 cards each containing a number from 1 to 9. You need to...
  2. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  3. How to Compute the Number of Pawns-Captures for Rook in Chess? On an 8 x 8 chessboard, there is one white rook. There also may be...
  4. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  5. Finding the Lucky Numbers in a Matrix Given a m * n matrix of distinct numbers, return all lucky numbers in the...
  6. How to Flatten 2D Vector in C++? Design and implement an iterator to flatten a 2d vector. It should support the following...
  7. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  8. Are Top 20 Witnesses Voting Each Other? Introducing Witness-voting Factor Let’s introduce a concept i.e. witness-voting factor that represent the average witness voting each other...

Leave a Reply