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.
This approach involves recursively dividing the preorder and postorder arrays to construct the tree. The first element of the preorder array is the root of the tree. The left subtree can be determined by identifying the position of the second element in preorder in the postorder array. Recursively apply this strategy for each subtree.
This solution defines the TreeNode class and implements a recursive method constructFromPrePost. The method splits the preorder and postorder lists to find left and right subtrees, creating TreeNode objects recursively. The base case checks for empty lists, indicating no subtree exists, thus returning None.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n^2) - Each split requires a scan operation which can take O(n) time. The recursion might stack as many times as there are elements, making this approach potentially expensive.
Space Complexity: O(n) - Due to the recursion stack and additional space required for the tree nodes.
This method optimizes the naive recursive approach by using a hash map to store the indices of values in the postorder sequence. By doing so, we can quickly find the index of the next root node, reducing the time complexity significantly. This way, the subtrees can be constructed in a more efficient manner by avoiding repeated searches.
The optimized Python approach uses a hash map to store the values and their indices in the postorder sequence. This allows for O(1) time complexity for querying indices in the postorder array. The recursive construct method builds the tree using the preIndex to track root values in preorder.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) - Hash map optimization reduces the search time significantly.
Space Complexity: O(n) - Due to the hash map and recursion stack.
| Approach | Complexity |
|---|---|
| Recursive Construction by Dividing Preorder and Postorder Arrays | Time Complexity: O(n^2) - Each split requires a scan operation which can take O(n) time. The recursion might stack as many times as there are elements, making this approach potentially expensive. Space Complexity: O(n) - Due to the recursion stack and additional space required for the tree nodes. |
| Recursive Approach with Hash Map Optimization | Time Complexity: O(n) - Hash map optimization reduces the search time significantly. Space Complexity: O(n) - Due to the hash map and recursion stack. |
| 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 |
construct binary tree from preorder and postorder traversal leetcode | leetcode 889 | dfs • Naresh Gupta • 17,592 views views
Watch 9 more video solutions →Practice Construct Binary Tree from Preorder and Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCode