Problem description:

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

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

For example, given

1
2
3
4
5
6
7
8
9
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution:

  1. First item in preorder is the current root. The value would divide the inorder list to left subtree and right subtree
  2. Python have list.index(value) to find index in O(n). Or could use dictionary.
  3. Be careful on the index.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if inorder:
            index = inorder.index(preorder.pop(0)) # first element in list is next node
            root = TreeNode(inorder[index])
            root.left = self.buildTree(preorder, inorder[:index])
            root.right = self.buildTree(preorder, inorder[index+1:]) 
            # starting from next node since inorder[index] is processed
            return root
1
2
3
4
5
6
7
     _______7______
    /              \
 __10__          ___2
/      \        /
4       3      _8
         \    /
          1  11

The preorder and inorder traversals for the binary tree above is:

preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}

First of all, we can see that preorder’s 1st element 7 is Root. The element 7 is the 4th element in inorder sequence. Since there is no duplicate in the sequence, there is no ambiguity.
The characteristic of inorder sequence is that it will follow this visit order left->root->right; therefore, we can see that the left elements before 7 is in left subtree. Other elements to the right must be in the right subtree.

Preorder traversal follows the sequence of root->left->right. Therefore, the left and right subtree’s preorder traversal must be {10, 4, 3, 1} and {2, 8, 11} respectively. Since the left and right subtree are binary trees in their own right, we can solve recursively!

Then how do we search the root value’s index in the inorder sequence?
If we use linear search, assume that the constructed binary tree is always balanced, then we can guarantee the run time complexity to be O(N log N), where N is the number of nodes. However, this is not necessarily the case and the constructed binary tree can be skewed to the left/right, which has the worst complexity of O(N^2).

A more efficient way is to eliminate the search by using an efficient look-up mechanism such as hash table. By hashing an element’s value to its corresponding index in the inorder sequence, we can do look-ups in constant time. Now, we need only O(N) time to construct the tree, which theoretically is the most efficient way.

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
/**
 * 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) {
        unordered_map<int, int> map;
        for (int i = 0; i < inorder.size(); i++) map[inorder[i]] = i;
        return buildTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, map);
    }
private:
    TreeNode* buildTree(vector<int>& preorder, int m1, int n1, vector<int>& inorder, int m2, int n2, unordered_map<int, int>& map) {
        if (m1 > n1) return NULL;
        int curindex = map[preorder[m1]];
        int new_right_m1 = m1 + curindex - m2 + 1;
        TreeNode *root = new TreeNode(preorder[m1]);
        root->left = buildTree(preorder, m1+1, new_right_m1-1, inorder, m2, curindex-1, map);
        root->right = buildTree(preorder, new_right_m1, n1, inorder, curindex+1, n2, map);
        return root;
    }