Construct Binary Tree from Preorder and Inorder Traversal

Hint:
A good way to attempt this question is to work backwards. Approach this question by drawing a binary tree, then list down its preorder and inorder traversal. As most binary tree problems, you want to solve this recursively.

About Duplicates:
In this solution, we will assume that duplicates are not allowed in the binary tree. Why?

Consider the following case:

preorder = [7, 7]
inorder =  [7, 7]

We can construct the following trees which are both perfectly valid solutions.

      7                     7
     /           or          \
    7                         7

Clearly, there would be ambiguity in constructing the tree if duplicates were allowed.

Solution:
Let us look at this example tree.

         _______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]

The crucial observation to this problem is the tree's root always coincides with the first element in preorder traversal. This must be true because in preorder traversal you always traverse the root node before its children. The root node's value appear to be 7 from the binary tree above.

We easily find that 7 appears as the 4^th index in the inorder sequence. (Notice that earlier we assumed that duplicates are not allowed in the tree, so there would be no ambiguity). For inorder traversal, we visit the left subtree first, then root node, and followed by the right subtree. Therefore, all elements left of 7 must be in the left subtree and all elements to the right must be in the right subtree.

We see a clear recursive pattern from the above observation. After creating the root node (7), we construct its left and right subtree from inorder traversal of [4, 10, 3, 1] and [11, 8, 2] respectively. We also need its corresponding preorder traversal which could be found in a similar fashion. If you remember, preorder traversal follows the sequence of root node, left subtree and followed by right subtree. Therefore, the left and right subtree's postorder 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!

We left out some details on how we search the root value's index in the inorder sequence. How about a simple linear search? If we 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²).

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.

For illustration purpose, the below code uses a simple array for table look-up, which is restricted to elements of 0 to 255 only. You should be able to extend it easily to use a hash table.

const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
    for (int i = 0; i < n; i++) {
        assert(0 <= inorder[i] && inorder[i] <= MAX-1);
        mapIndex[inorder[i]] = i;
    }
}

// precondition: mapToIndices must be called before entry
Node *buildInorderPreorder(int in[], int pre[], int n, int offset) {
    assert(n >= 0);
    if (n == 0) return NULL;
    int rootVal = pre[0];
    int i = mapIndex[rootVal]-offset;  // the divider's index
    Node *root = new Node(rootVal);
    root->left = buildInorderPreorder(in, pre+1, i, offset);
    root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1, offset+i+1);
    return root;
}

Now, if we are given inorder and postorder traversal, can we construct the binary tree?

The answer is yes, using very similar approach as above. Please see question Construct Binary Tree from Inorder and Postorder Traversal for more details.

Further Thoughts:

1. If we are given preorder and postorder traversal, can we construct the binary tree? Why or why not?
2. Given preorder, inorder, and postorder traversal, how can you verify if these traversals are referring to the exact same binary tree?
3. Remember from my earlier post: Serialization/Deserialization of a Binary Tree? It is trivial to see this as an alternative method to serialize/deserialize a binary tree. :)