Construct Binary Tree From Inorder and Preorder/Postorder Traversal

April 20, 2011 in binary tree

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


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 4th 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(N2).

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.

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. Below is the code:

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. :)
VN:F [1.9.22_1171]
Rating: 4.6/5 (45 votes cast)
Construct Binary Tree From Inorder and Preorder/Postorder Traversal, 4.6 out of 5 based on 45 ratings

58 responses to Construct Binary Tree From Inorder and Preorder/Postorder Traversal

  1. The post order could already recover the whole tree. While need inorder and post order together?

    In your Serialization/Deserialization of a Binary Tree, you also just use post order to recover. .

    VA:F [1.9.22_1171]
    -2
    • Postorder alone could not construct the binary tree, unless it is a sorted binary tree (BST). My example above purposely used an unordered binary tree to avoid assumption that the binary tree is sorted. To serialize/deserialize using preorder/postorder alone you have to store extra sentinels along with the nodes’ value.

      VN:F [1.9.22_1171]
      +9
  2. Can you clarify what exactly the offset and divider’s index are and their importance to the algorithm?

    VA:F [1.9.22_1171]
    0
    • The divider’s index is just the index of the root value in the inorder sequence.

      The offset is used for the mapIndex[] array only. mapIndex[] array maps a value to index in the inorder array. However, when we separate the tree into its right subtree, the corresponding inorder subarray is passed in as in+i+1. This alters the original index of the array and it won’t work if we use mapIndex[] directly. Therefore, we need to record the offset from the original array.

      VN:F [1.9.22_1171]
      +1
  3. What is the offset initially be called with. Can you pls provide the call method parameters.
    Thanks

    VA:F [1.9.22_1171]
    0
    • the initial offset should be zero.. the offset+i+1 is done since in+i+1 is done. Since we start with in+i+1, our indexes should be -(i+1).

      For implementation without offset and mapIndex check here

      But obviously, its slower than map version. :)

      VA:F [1.9.22_1171]
      0
  4. Contribute my code :

    #include
    #include

    using namespace std;

    struct node{
    node* left;
    node* right;
    int data;
    };

    node* root;

    void buildtree(node *b, int left_selected ,int* preorder, int* inorder){

    int preorder_1[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
    int preorder_2[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
    int inorder_1[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
    int inorder_2[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
    int i, j, k1, k2;

    //insert preorder[0];
    if(b==NULL){
    root = b = new node;
    b->data = preorder[0];
    b->left = b->right = NULL;
    }
    else{
    node* tmp = new node;
    tmp->data = preorder[0];
    tmp->left = tmp->right = NULL;
    if(left_selected)
    b->left = tmp;
    else
    b->right = tmp;
    b = tmp;
    }

    i = 0;
    while(inorder[i] != preorder[0]){
    inorder_1[i] = inorder[i];
    i++;
    }

    i++;
    j = 0;
    while(inorder[i] != -1 ){
    inorder_2[j] = inorder[i];
    j++;
    i++;
    }

    i = j = k1 = k2 = 0;
    while(preorder[i] != -1 ){

    i++;
    int flag = false;
    j = 0;
    while(inorder_1[j] != -1 ){
    if (inorder_1[j] == preorder[i]){
    flag = true;
    break;
    }
    j++;
    }

    if(flag){
    preorder_1[k1] = preorder[i];
    k1++;
    }
    else{
    preorder_2[k2] = preorder[i];
    k2++;
    }

    }

    if(preorder_1[0] != -1)
    buildtree(b, 1, preorder_1, inorder_1);
    if(preorder_2[0] != -1)
    buildtree(b, 0, preorder_2, inorder_2);

    }

    int main()
    {
    root = NULL;
    int preorder[] = {7,10,4,3,1,2,8,11,-1};
    int inorder[] = {4,10,3,1,7,11,8,2,-1};
    buildtree(root, 1 ,preorder, inorder);

    return 1;
    }

    VA:F [1.9.22_1171]
    0
  5. Following is my codes. The same algorithm as introduced here.

    template
    void binaryTree::constructTreeFromPreorderInorderSets()
    {
    vector preorderSet;
    vector inorderSet;
    cout <> numberNodes;
    cout << "Input preorder set one by one:" << endl;
    T tmp;
    for( int i = 0 ; i > tmp;
    preorderSet.push_back( tmp );
    }
    cout << "Input inorder set one by one:" << endl;
    for( int i = 0 ; i > tmp;
    inorderSet.push_back( tmp );
    }
    int p = 0;
    bool * nodeAdded = new bool[ numberNodes ];
    for( int i = 0 ; i < numberNodes; i ++ ) nodeAdded[i] = false;
    constructTreeRecurselyInorderPreorder( 0, numberNodes-1, p, root, preorderSet, inorderSet, nodeAdded, numberNodes );
    }

    template
    void binaryTree::constructTreeRecurselyInorderPreorder( int begin, int end, int & p, treeNode * & subroot, const vector & preorderSet, const vector & inorderSet, bool * nodeAdded, const int & numberNodes )
    {
    if( begin > end ) return;
    subroot = new treeNode( preorderSet[p], NULL, NULL );
    int i,j; //position of A[p] at set B (suppose A is preorder set, B is inorder set)
    //we must compare in each small segment: begin-end
    for( i = begin ; i = numberNodes )
    {
    cerr << "Error:" << "preorderSet["<<p<<"]=" << preorderSet[p]<leftChild, preorderSet, inorderSet, nodeAdded, numberNodes );
    constructTreeRecurselyInorderPreorder( j+1, end, p, subroot->rightChild, preorderSet, inorderSet, nodeAdded, numberNodes );
    }

    VA:F [1.9.22_1171]
    -2
  6. For problem 1 “If we are given preorder and postorder traversal, can we construct the binary tree? Why or why not?”, I think the answer is no, right? I think there will be problem with leaves whose parent has only 1 child because in such case such leaf can be either left or right child.

    VA:F [1.9.22_1171]
    +3
    • Hi,

      I have different answer however. Following is my explanation. How do you think?
      1. Given preorder and postorder traversal, we can still construct the binary tree. For the preorder, the first is root node, followed by nodes of the left subtree, followed by nodes of the right subtree. For the postorder, the last is root node, in front of which they are the nodes of the right subtree, in front of which they are the nodes of the left subtree. So, the second last element in the postorder will be the root node of the right subtree. Finding the position of the root node of the right subtree in the preorder, then the preorder can be partitioned into three parts: root node, followed by the nodes of the left subtree, followed by the nodes of the right subtree. The later two parts can be constructed into left subtree and right subtree respectively and recursively. For the post order, it can also be partitioned into three parts by coounting the number of nodes in each part. In fact, in recursion function, we always reconstruct the right subtree first and then left subtree, and decrease the index for postorder by one in each recursion. Then the index for the postorder will always point to the right element.
      //Then, Therefore, we can see that we can still construct the binary tree given the preorder and postorder
      //traversal.

      VA:F [1.9.22_1171]
      -2
      • but i am having some different answer.we can only construct full binary tree(all nodes except last leaf level two child nodes)and the strictly binary tree(if n leaf node then 2n-1 total nubers of nodes) if the preorder and post order is given.because for all the other trees post and pre order may be same but not the inorder is same.So the resultant tree may yield different structures for all binary tree except full binary and strictly binary tree.

        VA:F [1.9.22_1171]
        +2
    • Henian, forget my previous post. You are right. I agree with you now.

      VA:F [1.9.22_1171]
      +1
      • i want to represent in an array and it should perform the operations of inorder ,preorder,postorder with out using linked list and with out traversal it should be in an level wise.how can i ?

        VA:F [1.9.22_1171]
        +1
  7. How to answer the second question please: Given preorder, inorder, and postorder traversal, how can you verify if these traversals are referring to the exact same binary tree?

    Thanks!

    VA:F [1.9.22_1171]
    +1
    • A preorder, inorder or postorder traversal can come from more than two different binary trees. For example, given an inorder traversal {4, 2, 5, 1, 6, 3, 7}, any element can be viewed as the root node of the binary tree, generating different binary trees. So I don’t think we can verify if these traversals are referring to the exact same binary tree.

      VA:F [1.9.22_1171]
      0
  8. A little pythonic.


    def maketree(preorder, inorder):
    global tree
    if len(preorder) == 0:
    return None

    root = preorder[0]
    ind = inorder.index(root)
    linorder = filter(lambda x: inorder.index(x) ind, inorder)
    lpreorder = filter(lambda x: x in linorder, preorder)
    rpreorder = filter(lambda x: x in rinorder, preorder)
    tree[root] = [maketree(lpreorder, linorder), maketree(rpreorder, rinorder)]
    return root

    tree = {}
    pO = [7,10,4,3,1,2,8,11]
    iO = [4,10,3,1,7,11,8,2]
    maketree(pO, iO)
    print tree
    </code

    VA:F [1.9.22_1171]
    +4
  9. Can you give a logic answer for the second question?
    If we are given preorder and postorder traversal, can we construct the binary tree? Why or why not?

    VA:F [1.9.22_1171]
    +1
  10. Sorry, I mean *first question!

    VA:F [1.9.22_1171]
    -1
  11. I have C# variant of this code available at
    http://tryingout101.blogspot.com/2011/08/deserializing-binary-tree-from-inorder.html

    VA:F [1.9.22_1171]
    0
  12. Hi 1337,

    For the second problem in further thought, I don’t think we can verify if these traversals are referring to the exact same binary tree.

    A preorder, inorder or postorder traversal can come from more than two different binary trees.
    For example, given an inorder traversal {4, 2, 5, 1, 6, 3, 7}, any element can be viewed as the root node of the binary tree, generating different binary trees.

    How do you think?

    VA:F [1.9.22_1171]
    0
    • With preorder and inorder, we first construct a tree. Then we use postorder to print this tree, and compare the printout with our given postorder array. This way, we can verify the answer.

      VA:F [1.9.22_1171]
      0
  13. The code is a little hard to understand. I have tried to copy it and run the given code myself to get a better understanding. I am not sure how many of you have done this, but after my analyse, the code to build tree from inorder and preorder will give us the tree differently, which the last node 11 is the right node of 8. Can anyone verify this?

    const int TREE_SIZE = 8;
    int in_order[TREE_SIZE] = {4, 10, 3, 1, 7, 8, 11, 2};
    int pre_order[TREE_SIZE] = {7, 10, 4, 3, 1, 2, 8, 11};
    const int MAX = 256;
    int mapIndex[MAX];
    for (int i = 0; i < TREE_SIZE; i++)
    {
    mapIndex[in_order[i]] = i;
    }
    buildInorderPreorder( in_order, pre_order, TREE_SIZE, 0, mapIndex);

    VA:F [1.9.22_1171]
    0
  14. Minor bug: The method cannot deal with duplicate bcs the mapping will only record the last occurrence of number, the latter 2 in your example tree.

    VN:F [1.9.22_1171]
    -1
    • In my post, I already mentioned: “In this solution, we will assume that duplicates are not allowed in the binary tree.”

      VN:F [1.9.22_1171]
      +1
  15. Here is a Java Version of the same problem

    http://www.technicalypto.com/2011/12/reconstruct-binary-tree-given-its.html

    VA:F [1.9.22_1171]
    0
  16. Actually you can simplify it by remove argument in[ ]. Since you never actually use it in function.

    VA:F [1.9.22_1171]
    0
  17. it is too much complex!!!!

    VA:F [1.9.22_1171]
    0
  18. here is a slightly simpler to understand version of your solution:

    Node *buildInorderPreorder(int mapIndex[], int pre[], int lo, int hi) {
    if (hi left = buildInorderPreorder(mapIndex, pre+1, lo, i);
    root->right = buildInorderPreorder(mapIndex, pre+i-lo+1, i+1, hi);
    return root;
    }

    You dont really need the array in, because the only role of in is to determine the dividers index i, but i is more efficiently determined with the hash table mapIndex.
    Instead of n and offset, I think the algorithm is simpler to understand in terms of indices lo and hi. In each recursion step, the range (lo, hi) is divided into (lo,i) and (i+1,hi). The recursion ends when the range is empty.

    VA:F [1.9.22_1171]
    0
  19. VA:F [1.9.22_1171]
    0
  20. Has this question been really asked in an interview. It seems way too complicated. Am I the only one here thinking it is too much?

    VA:F [1.9.22_1171]
    0
  21. I mean even your code is not perfect.You use

    as a parameter in the methods and do pointer arithmetic passing it as argument in subsequent calls but this parameter is actually redudant and not used in the code.This makes the code not readable which IMO it is something important in an interview.

    VA:F [1.9.22_1171]
    +1
    • I think 1337 should delete the parameter “int[] in” in the recursion. in[] has no use after you got mapIndex array

      VN:F [1.9.22_1171]
      +1
  22. Hi 1337c0d3r, I found in your buildInorderPreorder, the use of the divider’s index and offset is a little complicated. Can I instead use the common (start, end) pair to specify the range? The only thing that need to be taken care of is when to increment the root’s index in the pre_order[]. The following is my code with the same algorithm. Please let me know if you find anything wrong.

    VN:F [1.9.22_1171]
    0
  23. Hi 1337c0d3r, if duplicates are allowed, is it possible to build a binary tree from Inorder and Preorder/Postorder Traversal ?

    VN:F [1.9.22_1171]
    0
  24. is it possible to reconstruct a unique tree from give anyone of three traversal order?

    VA:F [1.9.22_1171]
    0
  25. So according to you
    1) Search for ROOT
    2) Then on Left and Right sub tree apply Binery Search Tree

    Then the resulting tree would be :-

    7
    / \
    10 11
    / \
    4 8
    / /
    3 2
    /
    1
    Right ?

    VA:F [1.9.22_1171]
    0
  26. Ok ^^^ See my tree here :P

    VA:F [1.9.22_1171]
    -1
  27. May I simply say what a relief to uncover someone that truly understands what they’re talking about online. You certainly realize how to bring an issue to light and make it important. More and more people really need to read this and understand this side of your story. I was surprised that you’re not more popular given that you certainly have the gift.

    VA:F [1.9.22_1171]
    0
  28. In Java:
    (Recursive methods can be converted to in-place for further optimization)

    VA:F [1.9.22_1171]
    +1
  29. Here’s in place version of the same java implementation of mine:

    VA:F [1.9.22_1171]
    0
  30. For the linear search, when the tree is perfectly balanced, the time should be n/2 rather than logn, right?

    VA:F [1.9.22_1171]
    0
  31. Good day! I simply would like to give a massive thumbs up for the truly amazing information you
    have here for this subject post. I shall be coming back on the weblog for more
    soon.

    VA:F [1.9.22_1171]
    0
  32. This code contains a run-time error, modified code is as follows..

    int mapIndex[20];
    void mapToIndices()
    {
    for (int i = 0; i < cnt; i++)
    {
    mapIndex[inorder[i]] = i;
    }
    }

    // precondition: mapToIndices must be called before entry
    Node buildInorderPreorder(int in[], int pre[], int n)
    {
    if (n 1)
    {
    root->left = buildInorderPreorder(in, pre+1, i);
    root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1);
    }
    return root;
    }

    Node buildInorderPostorder(int in[], int post[], int n)
    {
    if (n 1)
    {
    root->left = buildInorderPostorder(in, post, i);
    root->right = buildInorderPostorder(in+i+1, post+i, n-i-1);
    }
    return root;
    }

    VN:F [1.9.22_1171]
    0
  33. i did this in no time and is a much easier way of solving this problem

    #include
    using namespace std;
    struct node
    {
    int data;
    node *left,*right;
    }*root;

    int inorder[]={4,10,3,1,7,11,8,2};
    int preorder[]={7,10,4,3,1,2,8,11};
    int j=0;

    node* check(int a,int b)
    {
    node *temp;
    temp=new node;
    if(a>b)
    return NULL;
    for(int i=a;idata=preorder[j++];
    temp->left=check(a,i-1);
    temp->right=check(i+1,b);
    }
    return temp;
    }

    void display(node *sr)
    {
    if(sr!=NULL)
    {
    cout<data<left);
    display(sr->right);
    }
    return;
    }

    int main()
    {
    root=NULL;
    root=check(0,7);
    cout<<"The preorder traversal: ";
    display(root);
    system("pause");
    return 0;
    }

    VA:F [1.9.22_1171]
    0
  34. simpler approach using binary search for root-val

    VN:F [1.9.22_1171]
    0
  35. simpler approach using binary search for root-val

    VN:F [1.9.22_1171]
    0
  36. Your explanation is very helpful.

    VA:F [1.9.22_1171]
    0
  37. answer to: if three orders are given, find whether they beling to the same tree of not
    First confirm if all the orders have the same number of elements.
    Using inorder and postrder, we can find preorder and after finding each element, we can compare it with the given preorder. If it does not match at any instant, it means the orders are not of a single BT

    VA:F [1.9.22_1171]
    0
  38. public class Solution {
    int pre;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    // Start typing your Java solution below
    // DO NOT write main() function
    pre = 0;
    if(preorder.length == 0){return null;}
    return build(preorder, inorder, 0, preorder.length-1);

    }

    public TreeNode build(int[] preorder, int[] inorder, int left, int right){
    if(left > right){
    return null;
    }
    //if(pre > preorder.length){
    // return null;
    //}
    int key = preorder[pre];
    pre++;
    TreeNode tn = new TreeNode(key);
    int i = 0;
    for(i = left; i <= right; i++){
    if(inorder[i] == key){break;}
    }

    tn.left = build(preorder, inorder, left, i-1);
    tn.right = build(preorder, inorder, i+1, right);

    return tn;
    }
    }

    VN:F [1.9.22_1171]
    0
  39. this is helpfull for practice…..

    VA:F [1.9.22_1171]
    0
  40. VN:F [1.9.22_1171]
    0
    • is it safe to remove these codes?

      VN:F [1.9.22_1171]
      0
  41. I agree with @SHawn, and some people else that in[] is not needed in the function

    . in[] is only used in the function

    .

    VN:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.