Construct Binary Tree from Preorder and Postorder Traversal

Problem Link

Construct Binary Tree from Preorder and Postorder Traversal – LeetCode

Problem: Construct Binary Tree from Preorder and Postorder Traversal

Problem Statement

Given two integer arrays preorder and postorder where:

• preorder is the preorder traversal of a binary tree.

• postorder is the postorder traversal of the same tree.

Construct and return any binary tree that fits these traversals.

Note: There can be multiple valid trees that satisfy the given traversals. You may return any such tree.

Examples

Example 1

Input:
preorder = [1,2,4,5,3,6,7]
postorder = [4,5,2,6,7,3,1]

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

Example 2

Input:
preorder = [1], 
postorder = [1]

Output:
 1

Constraints

• 1 <= preorder.length <= 30

• postorder.length == preorder.length

• All elements are unique

• Each input corresponds to a valid binary tree

Intuition

In preorder, the first element is the root.
In postorder, the last element is the root.

By comparing preorder and postorder arrays:

• The second element of preorder is the left child of root.

• Find the left child in postorder to determine the size of the left subtree.

We can use this information recursively to build the tree.

Approach

1. Use a preIndex starting at 0 to track the current root in preorder.

2. Build a hashmap from postorder values to their indices for O(1) lookup.

3. Recursively:

   • Pick current root from preorder[preIndex] and increment preIndex.

   • If the current subtree has more than one node:

     • Use preorder[preIndex] to identify the left child.

     • Find its index in postorder.

     • Recursively build the left and right subtrees.

   • Return the root.

Code (Java)

class Solution {
    private int preIndex = 0;
    private Map<Integer, Integer> postIndexMap;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        postIndexMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            postIndexMap.put(postorder[i], i);
        }

        return build(preorder, postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] postorder, int postStart, int postEnd) {
        TreeNode root = new TreeNode(preorder[preIndex++]);

        if (postStart == postEnd || preIndex >= preorder.length) {
            return root;
        }

        int leftRootVal = preorder[preIndex];
        int leftRootIndex = postIndexMap.get(leftRootVal);

        root.left = build(preorder, postorder, postStart, leftRootIndex);
        root.right = build(preorder, postorder, leftRootIndex + 1, postEnd - 1);

        return root;
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Each node is visited once, and postorder lookups are O(1) due to hashmap.

• Space Complexity: O(N)
  Hashmap + recursion stack

Dry Run

Input:

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

• preIndex = 0 → root = 1

• preIndex = 1 → left child = 2

  • Find index of 2 in postorder → index 2 → size of left subtree = 3

  • Recurse for subtree post[0:2] → [4,5,2]

• Continue recursively building left and right

Conclusion

• This is a classic recursive tree construction problem using preorder and postorder.

• Since inorder is not provided, multiple trees may match the traversal — the solution returns one valid tree.

• Important pattern for interview problems where partial traversal info is given.