Problem

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example

Example 1:

1
2
3
4
5

            3
           / \
          9   20
             /  \
            15   7

1
2

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Similar Problems

Construct Binary Tree from Inorder and Preorder Traversal Construct Binary Tree from Inorder and Level Order Traversal

Solution

Method 1 - Recursion

We can solve the problem similar to Construct Binary Tree from Inorder and Preorder Traversal.

Lets look at the binary tree:

1
2
3
4
5

         1
        / \
       2   3
      / \ / \
     4  5 6  7

The inorder and postorder traversal are:

1
2

inorder = [4, 2, 5, 1, 6, 3, 7]
postorder = [4, 5, 2, 6, 7, 3, 1]

How does postorder[] array helps? The last element in postorder[] acts as the root of the tree (in this case, 1).

How does inorder[] array helps? inorder[] helps determine the left and right subtrees of the root. Elements appearing before the root in inorder[] belong to the left subtree, while elements appearing after belong to the right subtree. In our case, it is [4, 2, 5] on left and [6, 3, 7] on right. (See picture below).

Code

 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

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Call the recursive function with full arrays and return the result
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        // Base case
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        
        // Find the root node from the last element of postorder traversal
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        
        // Find the index of the root node in inorder traversal
        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }
        
        // Recursively build the left and right subtrees
        int leftSize = rootIndex - inStart;
        int rightSize = inEnd - rootIndex;
        root.left = buildTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
        root.right = buildTree(inorder, rootIndex + 1, inEnd, postorder, postEnd - rightSize, postEnd - 1);
        
        return root;
    }
}