Construct binary tree from inorder and postorder traversals

Given Inorder and postorder traversals of a binary tree with no duplicate node values, how can you construct a binary tree which generates these traversal arrays?

For example, if we are given following two arrays -          
inorder = [4,2,5,1,6,3,7] and postorder = [4,5,2,6,7,3,1] we need to construct following tree.

                1
         2             3
      4    5        6     7


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

We will try to understand this algorithm using an example.
Say we are given following two arrays -
postorder = [4,5,2,6,7,3,1]
inorder = [4,2,5,1,6,3,7]

Now what we know is post-order traversal visits tree in L-R-N fashion (L:left sub-tree, R:right sub-tree, N:node) and in-order traversal visits tree in L-N-R fashion. With this is mind, if we now look at the above postorder array, we can say that node '1' must be the root of the tree. Now for the tree with '1' as the root, we will try to construct left and right sub-trees. To find the nodes in left and right sub-trees we make use of the given in-order array. Because in-order traversal visits tree in L-N-R fashion, if we find the node '1' in the in-order array, all the elements to the left of element '1' in the in-order array will be in the left sub-tree and all the elements to the right of element '1' will be in the right sub-tree. Note that sub-arrays formed by elements which are to the left and to the right of '1' are also in-order traversals of left and right sub-tress of the tree with root as 1.

Basically, we need to construct left sub-tree of '1' using in-order array [4,2,5] and we need to construct right sub-tree of '1' using in-order array [6,3,7].
Since the left sub-tree would be constructed using array[4,2,5], we know that left sub-tree has 3 nodes in it. Similarly, right sub-tree has 3 nodes in it(array[6,3,7]). Now that we know the number of nodes in sub-trees, we can decide which part of the post-order array would go in right sub-tree and which part in left. Since, post-order traversal does a L-R-N visit, 3 elements before the last element would go in right sub-tree and 3 elements before that(first three elements) would go in left sub-tree. In other words, post-order array for left sub-tree would be [4,5,2] and post-order array for right sub-tree would be [6,7,3].

Using this information, we can reduce the given problem to constructing a tree with node '1' as the root with its left sub-tree having in-order array as [4,2,5] and post-order array as [4,5,2]; and its right sub-tree having in-order array as [6,3,7] and post-order array as [6,7,3]. Notice that problems of constructing right and left sub-trees have similar problem definitions as the original problem but with reduced array sizes. Therefore, we need to use recursion to solve the original problem. The base case for this recursive problem would be that if the arrays are empty we will return null tree.

The steps of this recursive algorithm are as following -
1. Call createTree(inorderArray = inorder,lowInorder = 0,highInorder = inorder.length-1,postorderArray = postorder,lowPostorder = 0, highPostorder = postorder.length - 1)
2. If (lowInorder > highIorder) or (lowPostorder > highPostorder) then we know that we have hit the base case and we return null tree.
3. Else,
3a. We create a root with value as postorder[highPostorder]
3b. We search for root node's value in the in-order array and find out the index of this root node in the in-order array. Let's call this index divideIndex.
* All the elements in the in-order array starting from the lowInorder index up to and excluding divideIndex are in left sub-tree and all the elements in the in-order array starting from the divideIndex+1 up to and including highInorder index are in the right sub-tree.
3c. Using the size of left sub-tree and right sub-tree we find out the correct indices in the post-order array for left sub-tree and the right sub-tree. Using these indices we make a recursive call, where we set

root.right = createTree(inorder, divideIndex + 1, highInorder,postorder, highPostorder-sizeOfRightSubTree, highPostorder - 1);

and

root.right = createTree(inorder, lowInorder, divideIndex - 1, postorder, highPostorder-sizeOfRightSubTree-sizeOfLeftSubTree, highPostorder-sizeOfRightSubTree-1);

4. After the recursive steps in step 3, our tree is completely constructed and we return the root to the calling function.

Worst case time complexity of this algorithm is O(n^2) when the tree that needs to be constructed is skewed as shown below.

                1
            2
        3
     4      
    
This recursive algorithm is implemented in the createTree function below. Please checkout code and algorithm visualization section for more details of the algorithm.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given Inorder and postorder traversals of a binary tree with no duplicate node values, 
 * how can you construct a binary tree which generates these traversal arrays? 
 * @author Nilesh
 */

public class ConstructBinaryTreeFromInorderAndPostorder {

    class TreeNode
    {
        TreeNode left;
        TreeNode right;
        int val;
    
        public TreeNode(int x)
        {
            this.val = x;
        }
    }
    
    
    int searchInorder(int val, int[] inorder, int lowInorder, int highInorder)
    {
        int i = lowInorder;
        for (; i <= highInorder; i++)
        {
            if (val == inorder[i]) break;
        }
        return i;
    }
    
    
    TreeNode createTree(int[] inorder, int lowInorder, int highInorder, int[] postorder, int lowPostorder, int highPostorder)
    {
        
        if ((lowInorder > highInorder) || (lowPostorder > highPostorder)) return null;
        
        TreeNode root = new TreeNode(postorder[highPostorder]);
        
        int divideIndex = searchInorder(root.val, inorder, lowInorder, highInorder);
        
        int sizeOfLeftSubTree = divideIndex - lowInorder;
        int sizeOfRightSubTree = highInorder - divideIndex;
        
        root.right = createTree(inorder, divideIndex + 1, highInorder, 
                                postorder, highPostorder-sizeOfRightSubTree, highPostorder-1 );
                              
                            
        root.left = createTree(inorder, lowInorder, divideIndex - 1,
                                postorder, highPostorder-sizeOfRightSubTree-sizeOfLeftSubTree, highPostorder-sizeOfRightSubTree-1);  
                                
        return root;                                
    }
    
    public TreeNode buildTree(int[] postorder, int[] inorder) {
        return createTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    
    private void printInorder(TreeNode root)
    {
        if (root == null) return;
        
        printInorder(root.left);
        System.out.print(" "+ root.val + ",");
        printInorder(root.right);
    }
    
    private void printPostorder(TreeNode root)
    {
        if (root == null) return;
        
        printPostorder(root.left);
        printPostorder(root.right);
        System.out.print(" "+ root.val + ",");
    }
    
    public static void main(String[] args)
    {
        ConstructBinaryTreeFromInorderAndPostorder solution = new ConstructBinaryTreeFromInorderAndPostorder();

        /*
                1
          2            3
        4   5        6    7
        */
        
        int[] inorder = {4,2,5,1,6,3,7};
        
        int[] postorder = {4,5,2,6,7,3,1};

        TreeNode root = solution.buildTree(postorder, inorder);
        System.out.print("Inorder array is:");
        solution.printInorder(root);
        
        System.out.println("");
        
        System.out.print("postorder array is:");
        solution.printPostorder(root);
    }
}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer