Home
Algorithm to Construct Binary Tree from Preorder and Inorder Traversal
Tags:, , , ,

Algorithm to Construct Binary Tree from Preorder and Inorder Traversal

July 23, 2019 No Comments algorithms, c / c++, DFS, recursive

Given preorder and inorder traversal of a tree, construct the binary tree. You may assume that duplicates do not exist in the tree.

For example, given

1
2

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

How to Construct the Binary Tree using Divide-and-Conquer Algorithm?

The root element is located the first in a binary tree’s preorder. Thus, we can iterate the inorder to find the index of the root element, then, we know the left and right part of the inorder traversal. Then, going back to the preorder, we can also find the separation between left and right tree. Recursively, we can construct the left and right tree.

However, a first naive implementation is as follows C++, which is inefficient as the intermediate vectors are copied. And we have done some clumbsy work (remembering the left tree in the hash set) to find the separation point. 

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/**
 * 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>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;    
        int n = preorder.size();
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[0]);
        // push elements to set before root in inorder
        int i = 0;
        unordered_set<int> inorder_left_set;        
        vector<int> inorder_left;
        while (i < n) {
            if (inorder[i] == root->val) break;
            inorder_left_set.insert(inorder[i]);
            inorder_left.push_back(inorder[i]);
            i ++;
        }
        // and the right part of the inorder
        vector<int> inorder_right;
        while (i < n) {
            inorder_right.push_back(inorder[i]);
            i ++;
        } 
        // now push all nodes in set to preorder left
        int j = 1;
        vector<int> preorder_left;
        while (j < n) {
            if (!inorder_left_set.count(preorder[j])) break;
            preorder_left.push_back(preorder[j]);
            j ++;
        }
        // the right tree of the preorder
        vector<int> preorder_right;
        while (j < n) {
            preorder_right.push_back(preorder[j]);
            j ++;
        }
        // recursively construct left tree        
        root->left = buildTree(preorder_left, inorder_left);
        // recursively construct right tree
        root->right = buildTree(preorder_right, inorder_right);
        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>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;    
        int n = preorder.size();
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[0]);
        // push elements to set before root in inorder
        int i = 0;
        unordered_set<int> inorder_left_set;        
        vector<int> inorder_left;
        while (i < n) {
            if (inorder[i] == root->val) break;
            inorder_left_set.insert(inorder[i]);
            inorder_left.push_back(inorder[i]);
            i ++;
        }
        // and the right part of the inorder
        vector<int> inorder_right;
        while (i < n) {
            inorder_right.push_back(inorder[i]);
            i ++;
        } 
        // now push all nodes in set to preorder left
        int j = 1;
        vector<int> preorder_left;
        while (j < n) {
            if (!inorder_left_set.count(preorder[j])) break;
            preorder_left.push_back(preorder[j]);
            j ++;
        }
        // the right tree of the preorder
        vector<int> preorder_right;
        while (j < n) {
            preorder_right.push_back(preorder[j]);
            j ++;
        }
        // recursively construct left tree        
        root->left = buildTree(preorder_left, inorder_left);
        // recursively construct right tree
        root->right = buildTree(preorder_right, inorder_right);
        return root;
    }
};

A better implementation is as follows, based on the same algorithm. We define a helper function take takes 4 extra integer parameters to define the ranges of the traversal vectors – thus avoiding copying the vectors. Also, after finding the index of the root element in the inorder traversal, we can compute the number of nodes in the left tree, thus a quicker way to find the separation in the preorder traversal.

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>& preorder, vector<int>& inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
private:
    TreeNode* buildTree(vector<int>& preorder, int a, int b, vector<int>& inorder, int c, int d) {
        if (a > b) return nullptr;
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[a]);
        // find the root position in inorder
        int i = c;
        while (i <= d) {
            if (inorder[i] == root->val) break;
            i ++;
        }
        int leftcnt = i - c - 1;
        a ++;
        // recursively construct left tree        
        root->left = buildTree(preorder, a, a + leftcnt, inorder, c, c + leftcnt);
        // recursively construct right tree
        root->right = buildTree(preorder, a + leftcnt + 1, b, inorder, i + 1, d);
        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>& preorder, vector<int>& inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
private:
    TreeNode* buildTree(vector<int>& preorder, int a, int b, vector<int>& inorder, int c, int d) {
        if (a > b) return nullptr;
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[a]);
        // find the root position in inorder
        int i = c;
        while (i <= d) {
            if (inorder[i] == root->val) break;
            i ++;
        }
        int leftcnt = i - c - 1;
        a ++;
        // recursively construct left tree        
        root->left = buildTree(preorder, a, a + leftcnt, inorder, c, c + leftcnt);
        // recursively construct right tree
        root->right = buildTree(preorder, a + leftcnt + 1, b, inorder, i + 1, d);
        return root;
    }    
};

The time complexity is O(N) where N nodes will be visited once during the process of constructing the binary tree. You can also use the similar algorithm to convert to a binary tree from its’ postorder and inorder sequences: How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?

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...
1043 words
Last Post: The 24 Game Algorithm using Depth First Search
Next Post: How to Generate Parentheses using Bruteforce or Depth First Search (Backtracking) Algorithms?

The Permanent URL is: Algorithm to Construct Binary Tree from Preorder and Inorder Traversal

Related posts:

  1. 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...
  2. How to Flatten 2D Vector in C++? Design and implement an iterator to flatten a 2d vector. It should support the following...
  3. 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...
  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. Compute the Number Spiral Diagonals Starting with the number 1 and moving to the right in a clockwise direction a...
  7. How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)? Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may...
  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