Construct Binary Tree from Inorder and Postorder Traversal - Video Solutions

Problem Overview: Given two arrays representing the inorder and postorder traversal of a binary tree, reconstruct the original tree. Every value is unique, so the tree structure can be determined by splitting the traversals correctly.

Approach 1: Recursive Divide and Conquer (Naive) (Time: O(n^2), Space: O(n))

The last element in postorder is always the root of the current subtree. Find that value in the inorder array to split the tree into left and right subtrees. Recursively repeat the process for each side. The inefficiency comes from scanning the inorder array every time you look up the root index, which can take O(n) per recursive call. This approach demonstrates the core divide-and-conquer idea but becomes slow for large trees.

Approach 2: Recursive Approach using HashMap (Time: O(n), Space: O(n))

Store each value's index from the inorder array in a hash map for constant-time lookup. Start from the last element of postorder to identify the root. Use the index from the map to determine how many nodes belong to the left and right subtrees. Recursively build the right subtree first, then the left subtree, because postorder processes nodes in left-right-root order. Each node is processed once and each lookup is O(1), giving linear time complexity. This method combines recursion with a hash table and standard divide and conquer tree construction.

Approach 3: Iterative Approach using Stack (Time: O(n), Space: O(n))

An iterative method simulates the recursive construction using a stack. Traverse the postorder array from the end while tracking the inorder pointer. Each new value becomes either the right child of the current node or the left child of the last node whose value matches the inorder pointer. The stack keeps track of nodes whose left subtree has not been assigned yet. This approach avoids recursion and can be easier to control in languages where recursion depth is limited. It still processes each node once and relies on properties of binary tree traversals.

Recommended for interviews: The recursive HashMap approach is the expected solution. Interviewers want to see that you recognize the root position in postorder and use a hash map to avoid repeated scans of the inorder array. Showing the naive version first demonstrates understanding of the traversal relationship, but optimizing it to O(n) with constant-time index lookups shows strong problem-solving skills.