Construct Binary Tree from Preorder and Postorder Traversal - Solution & Explanation
Problem Statement
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.length- All the values of
preorderare unique. postorder.length == preorder.length1 <= postorder[i] <= postorder.length- All the values of
postorderare unique. - It is guaranteed that
preorderandpostorderare the preorder traversal and postorder traversal of the same binary tree.
Approach Overview
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 1: Recursive Construction by Dividing Preorder and Postorder Arrays
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.
Code
Python
C++
Java
C#
JavaScript
Complexity
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.
Approach 2: Recursive Approach with Hash Map Optimization
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.
Code
Python
C++
Java
C#
JavaScript
Complexity
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 3: Recursion
The order of pre-order traversal is: root node -> left subtree -> right subtree, and the order of post-order traversal is: left subtree -> right subtree -> root node.
Therefore, the root node of the binary tree must be the first node of the pre-order traversal and the last node of the post-order traversal.
Next, we need to determine the range of the left and right subtrees of the binary tree.
If the binary tree has a left subtree, then the root node of the left subtree must be the second node of the pre-order traversal; if the binary tree does not have a left subtree, then the second node of the pre-order traversal must be the root node of the right subtree. Since the results of post-order traversal in these two cases are the same, we can take the second node of the pre-order traversal as the root node of the left subtree, and then find its position in the post-order traversal, so as to determine the range of the left subtree.
Specifically, we design a recursive function dfs(a, b, c, d), where [a, b] represents the range of pre-order traversal, and [c, d] represents the range of post-order traversal. The function of this function is to construct the root node of the binary tree based on the pre-order traversal [a, b] and the post-order traversal [c, d]. The answer is dfs(0, n - 1, 0, n - 1), where n is the length of the pre-order traversal.
The execution steps of the function dfs(a, b, c, d) are as follows:
- If
a > b, the range is empty, return a null node directly. - Otherwise, we construct a new node
root, its value is the value of the first node in the pre-order traversal, which ispreorder[a]. - If
aequalsb, it means thatroothas neither a left subtree nor a right subtree, returnrootdirectly. - Otherwise, the value of the root node of the left subtree is
preorder[a + 1], we find the position ofpreorder[a + 1]in the post-order traversal, denoted asi. The number of nodes in the left subtreem = i - c + 1, from this we know that the range of the left subtree in the pre-order traversal is[a + 1, a + m], the range in the post-order traversal is[c, i], the range of the right subtree in the pre-order traversal is[a + m + 1, b], and the range in the post-order traversal is[i + 1, d - 1]. - Knowing the range of the left and right subtrees, we can recursively rebuild the left and right subtrees, and then make the root nodes of the left and right subtrees as the left and right child nodes of
rootrespectively. Finally returnroot.
In the function dfs(a, b, c, d), we need to use a hash table pos, which stores the position of each node in the post-order traversal. At the beginning of the function, we can calculate this hash table first, so that we can find the position of any node in the post-order traversal in O(1) time.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Another Recursive Approach
We can design a recursive function dfs(i, j, n), where i and j represent the starting points of the pre-order and post-order traversals, respectively, and n represents the number of nodes. This function constructs the root node of the binary tree based on the pre-order traversal [i, i + n - 1] and post-order traversal [j, j + n - 1]. The answer is dfs(0, 0, n), where n is the length of the pre-order traversal.
The execution steps of the function dfs(i, j, n) are as follows:
- If
n = 0, the range is empty, so return a null node directly. - Otherwise, we construct a new node
root, whose value is the value of the first node in the pre-order traversal, which ispreorder[i]. - If
n = 1, it means thatroothas neither a left subtree nor a right subtree, so returnrootdirectly. - Otherwise, the value of the root node of the left subtree is
preorder[i + 1]. We find the position ofpreorder[i + 1]in the post-order traversal, denoted ask. Then the number of nodes in the left subtree ism = k - j + 1, and the number of nodes in the right subtree isn - m - 1. We recursively rebuild the left and right subtrees, and then make the root nodes of the left and right subtrees the left and right child nodes ofroot, respectively. Finally, returnroot.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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. |
| Recursion | — |
| Another Recursive Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Construct Binary Tree from Preorder and Postorder Traversal - Leetcode 889 - Python • NeetCodeIO • 16,727 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Construct Binary Tree from Preorder and Postorder Traversal easy or hard?
Construct Binary Tree from Preorder and Postorder Traversal Python/Java solution
How to solve Construct Binary Tree from Preorder and Postorder Traversal in O(n)?
What is the best approach for Construct Binary Tree from Preorder and Postorder Traversal?
Is Construct Binary Tree from Preorder and Postorder Traversal asked at Google/Amazon/Meta?
What data structure is used in Construct Binary Tree from Preorder and Postorder Traversal?
What is the time complexity of Construct Binary Tree from Preorder and Postorder Traversal?
Ready to solve this problem?
Practice Construct Binary Tree from Preorder and Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCode