Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.
If there exist multiple answers, you can return any of them.
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 <= 301 <= preorder[i] <= preorder.lengthpreorder are unique.postorder.length == preorder.length1 <= postorder[i] <= postorder.lengthpostorder are unique.preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.The key idea in #889 Construct Binary Tree from Preorder and Postorder Traversal is understanding how traversal orders define subtree boundaries. In preorder, the first element is always the root, while postorder places the root at the end of the traversal. Using this property, we can recursively divide the tree into left and right subtrees.
After identifying the root from preorder, the next element represents the root of the left subtree. By locating this value in the postorder array (often using a hash map for quick index lookup), we can determine the size of the left subtree. This allows us to split both arrays into segments corresponding to the left and right subtrees.
A divide and conquer recursion builds the tree node by node until the segments are exhausted. Using a hash table avoids repeated scans and keeps the algorithm efficient. The optimized solution runs in O(n) time with O(n) space due to recursion and auxiliary mappings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Divide and Conquer with Hash Map | O(n) | O(n) |
Jenny's Lectures CS IT
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, tree construction problems based on traversal orders are common in technical interviews at companies like Amazon, Google, and Meta. They test understanding of recursion, tree properties, and efficient use of hash maps.
Preorder and postorder alone do not always uniquely define a binary tree because they don't explicitly show where left and right subtree boundaries split. However, the problem guarantees that at least one valid binary tree can be constructed.
A hash map is commonly used to store value-to-index mappings for the postorder traversal. This allows constant-time lookups when determining subtree boundaries during recursive construction of the binary tree.
The optimal approach uses divide and conquer with recursion. The first element in preorder is the root, and the next element identifies the left subtree root, whose index in postorder determines subtree size. A hash map is often used to quickly locate indices and build the tree efficiently.