Watch 10 video solutions for Construct Binary Tree from Preorder and Postorder Traversal, a medium level problem involving Array, Hash Table, Divide and Conquer. This walkthrough by Naresh Gupta has 17,592 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You receive two arrays representing the preorder and postorder traversal of a binary tree. The task is to reconstruct any valid binary tree that produces these traversals. Since preorder processes root → left → right and postorder processes left → right → root, the root is easy to identify but determining subtree boundaries requires careful indexing.
Approach 1: Recursive Construction by Dividing Preorder and Postorder Arrays (O(n²) time, O(h) space)
This method builds the tree using recursive partitioning of the traversal arrays. The first value in preorder is always the root. The next value in preorder represents the left subtree's root. Search for this value in the postorder array to determine how many nodes belong to the left subtree. Once you know the subtree size, recursively construct the left and right children using sliced index ranges of both arrays. The logic mirrors how preorder and postorder traverse the tree. However, repeatedly scanning the postorder array to locate subtree boundaries leads to O(n²) time in the worst case, especially for skewed trees. Space complexity is O(h) from recursion depth where h is tree height.
Approach 2: Recursive Approach with Hash Map Optimization (O(n) time, O(n) space)
The optimization removes repeated searches in the postorder array. Before recursion, build a hash map from node value to its index in postorder. Now when preorder identifies the root and the next value as the left subtree root, you can find its position in O(1) using a hash lookup. That index directly tells you the size of the left subtree. Recursively build left and right subtrees using index boundaries without copying arrays. Each node is processed once, giving O(n) time complexity. The map requires O(n) space and recursion still uses O(h) stack space. This approach fits naturally with divide and conquer recursion and efficient indexing.
The solution relies heavily on traversal properties of a tree and the structure of a binary tree. Preorder always exposes the root first, while postorder reveals subtree completion. Combining both lets you reconstruct subtree boundaries.
Recommended for interviews: The hash map optimized recursive approach. Interviewers expect you to recognize that repeated index searches are inefficient and replace them with constant‑time lookups. Implementing the plain recursive partition first shows understanding of traversal relationships, while the optimized version demonstrates algorithmic maturity and time complexity awareness.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Construction by Dividing Arrays | O(n²) | O(h) | Useful for understanding traversal relationships and simple recursive reconstruction logic |
| Recursive Approach with Hash Map Optimization | O(n) | O(n) | Preferred for interviews and large inputs where repeated searches must be avoided |