Construct Binary Tree from Inorder and Postorder Traversal - Video Solutions

Problem Overview: You are given two traversal arrays of the same binary tree: inorder and postorder. The goal is to reconstruct the original binary tree. The challenge is determining how to split the tree correctly using the ordering properties of both traversals.

Approach 1: Recursive Divide and Conquer with HashMap (O(n) time, O(n) space)

The key observation comes from traversal properties. In postorder, the last element is always the root of the current subtree. Once you identify the root, you locate its position inside the inorder array. Everything to the left of that index belongs to the left subtree, and everything to the right belongs to the right subtree. To avoid repeatedly scanning the inorder array, store each value's index in a HashMap for constant-time lookups.

The algorithm processes the postorder array from the end. Each recursive call creates a node, splits the inorder range, and recursively builds the right subtree first, then the left subtree. Building the right subtree first is necessary because postorder processes nodes as left → right → root, so when iterating backwards the order becomes root → right → left. Each node is created exactly once, producing O(n) time complexity with O(n) space for recursion and the hash map. This approach combines divide and conquer with efficient lookups using a hash table.

Approach 2: Iterative Construction using Stack (O(n) time, O(n) space)

An iterative strategy avoids recursion by simulating the construction process with a stack. Start from the last element of postorder, which is the root, and push it onto the stack. Traverse the postorder array backwards while tracking an index in the inorder array. The stack represents the path of nodes whose left child hasn't been attached yet.

If the top of the stack doesn't match the current inorder value, the next node becomes the right child of the stack's top node. If it matches, pop nodes from the stack until the values diverge; the next created node becomes the left child of the last popped node. This mirrors how inorder traversal signals that the right subtree has finished and the algorithm should move left. Each node is pushed and popped at most once, giving O(n) time complexity and O(n) auxiliary stack space. The approach is useful when you want to avoid deep recursion while working with binary tree construction problems.

Recommended for interviews: The recursive HashMap approach is the expected solution. It clearly demonstrates understanding of traversal properties and divide and conquer. Interviewers usually want to see the insight that the last element of postorder is the root and that a hash map reduces the lookup cost to O(1). The iterative stack version shows deeper mastery but is less commonly expected as the primary solution.