LeetCode 889 - Construct Binary Tree from Preorder and Postorder Traversal
The problem gives us two traversal orders of the same binary tree: - preorder, which visits nodes in the order: root → left subtree → right subtree - postorder, which visits nodes in the order: left subtree → right subtree → root Our task is to reconstruct and return the…
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree
Solution
Problem Understanding
The problem gives us two traversal orders of the same binary tree:
preorder, which visits nodes in the order:
root → left subtree → right subtree
postorder, which visits nodes in the order:
left subtree → right subtree → root
Our task is to reconstruct and return the binary tree that produced these traversals.
An important detail is that all node values are distinct. This matters because it allows us to uniquely identify where a subtree begins and ends based on node values. Without distinct values, reconstruction would become ambiguous.
The problem also states that if multiple valid trees exist, we may return any of them. This is important because preorder and postorder traversals alone do not always uniquely determine a binary tree. For example, if a node has only one child, we cannot determine whether that child is a left child or a right child from these traversals alone. The problem accepts any valid reconstruction.
The constraints are relatively small:
1 <= n <= 30- all values are unique
- both arrays are valid traversals of the same tree
Even though the input size is small enough that less efficient solutions could pass, the problem is fundamentally about understanding traversal properties and recursive tree construction.
Several edge cases are important:
- A tree with only one node.
- A skewed tree where every node has only one child.
- A perfectly balanced tree.
- Recursive boundary conditions where a subtree becomes empty.
- Correctly identifying subtree sizes from traversal boundaries.
A naive implementation can easily make off-by-one mistakes when slicing traversal ranges or incorrectly determining subtree boundaries.
Approaches
Brute Force Approach
A brute force strategy would attempt to recursively try every possible way to split the traversals into left and right subtrees.
The preorder traversal always starts with the root, while the postorder traversal always ends with the root. However, without additional information, we do not initially know how many nodes belong to the left subtree versus the right subtree.
A brute force solution could try all possible subtree sizes, recursively validate whether the generated traversals match, and return a valid tree once found.
This works because eventually one partitioning will correspond to a valid tree structure. However, the number of possible partitions grows exponentially, making this approach impractical for larger inputs.
Optimal Recursive Divide and Conquer Approach
The key observation is that traversal properties allow us to determine subtree boundaries efficiently.
In preorder traversal:
[root][left subtree][right subtree]
In postorder traversal:
[left subtree][right subtree][root]
After identifying the root from preorder, the next preorder value must be the root of the left subtree, assuming a left subtree exists.
If we know the left subtree root value, we can locate it inside the postorder traversal. Everything before and including that value belongs to the left subtree. This immediately gives us the size of the left subtree.
Once we know the subtree size, we can recursively construct:
- the left subtree
- the right subtree
A hash map allows constant-time lookup of node positions in postorder traversal, reducing the overall complexity to linear time.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Tries many subtree partition combinations recursively |
| Optimal | O(n) | O(n) | Uses preorder/postorder properties with hashmap-assisted recursion |
Algorithm Walkthrough
Optimal Recursive Construction
- Start with the first element of the current preorder range.
In preorder traversal, the first element is always the root of the current subtree. Create a tree node using this value. 2. Handle the base case.
If the current subtree range contains only one node, return that node immediately. This prevents unnecessary recursion. 3. Identify the left subtree root.
After the root in preorder traversal, the next element must belong to the left subtree, if a left subtree exists.
For example:
preorder = [1, 2, 4, 5, 3, 6, 7]
^
root
^
left subtree root
- Find the left subtree boundary in postorder traversal.
Use a hash map storing:
value -> index in postorder
This lets us instantly locate the left subtree root inside postorder traversal. 5. Compute the left subtree size.
In postorder traversal, all nodes up to the left subtree root belong to the left subtree.
Example:
postorder = [4, 5, 2, 6, 7, 3, 1]
^
left subtree root
Left subtree size:
left_size = left_root_index - post_left + 1
- Recursively build the left subtree.
Use the computed subtree size to determine the correct preorder and postorder ranges. 7. Recursively build the right subtree.
Everything remaining after the left subtree belongs to the right subtree. 8. Return the constructed root node.
Why it works
The algorithm relies on two traversal invariants:
- preorder always reveals the root first
- postorder always reveals subtree completion order
By taking the next preorder value as the left subtree root and locating it in postorder traversal, we can precisely determine subtree boundaries. Every recursive call works on smaller valid traversal ranges, ensuring the entire tree is reconstructed correctly.
Python Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import List, Optional
class Solution:
def constructFromPrePost(
self,
preorder: List[int],
postorder: List[int]
) -> Optional[TreeNode]:
post_index = {
value: idx for idx, value in enumerate(postorder)
}
def build(
pre_left: int,
pre_right: int,
post_left: int,
post_right: int
) -> Optional[TreeNode]:
if pre_left > pre_right:
return None
root = TreeNode(preorder[pre_left])
if pre_left == pre_right:
return root
left_root_value = preorder[pre_left + 1]
left_root_index = post_index[left_root_value]
left_subtree_size = left_root_index - post_left + 1
root.left = build(
pre_left + 1,
pre_left + left_subtree_size,
post_left,
left_root_index
)
root.right = build(
pre_left + left_subtree_size + 1,
pre_right,
left_root_index + 1,
post_right - 1
)
return root
return build(
0,
len(preorder) - 1,
0,
len(postorder) - 1
)
The solution begins by constructing a hash map from node value to its index in the postorder traversal. This avoids repeatedly scanning the array during recursive calls.
The build function reconstructs a subtree using index boundaries rather than slicing arrays. This is important because slicing creates additional copies and increases memory overhead.
The first preorder element is always chosen as the subtree root.
If the subtree contains only one node, the function immediately returns it. This is the recursion base case.
Otherwise, the algorithm identifies the left subtree root from preorder[pre_left + 1]. Using the hash map, it locates this node in postorder traversal and calculates the subtree size.
The recursion then constructs left and right subtrees using carefully computed index ranges.
Finally, the root node with its attached subtrees is returned.
Go Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
postIndex := make(map[int]int)
for i, val := range postorder {
postIndex[val] = i
}
var build func(
int,
int,
int,
int,
) *TreeNode
build = func(
preLeft int,
preRight int,
postLeft int,
postRight int,
) *TreeNode {
if preLeft > preRight {
return nil
}
root := &TreeNode{
Val: preorder[preLeft],
}
if preLeft == preRight {
return root
}
leftRootValue := preorder[preLeft+1]
leftRootIndex := postIndex[leftRootValue]
leftSubtreeSize := leftRootIndex - postLeft + 1
root.Left = build(
preLeft+1,
preLeft+leftSubtreeSize,
postLeft,
leftRootIndex,
)
root.Right = build(
preLeft+leftSubtreeSize+1,
preRight,
leftRootIndex+1,
postRight-1,
)
return root
}
return build(
0,
len(preorder)-1,
0,
len(postorder)-1,
)
}
The Go implementation follows the same recursive logic as the Python version.
The main language-specific difference is that Go uses pointers for tree nodes, so subtree assignments use *TreeNode.
Go also requires explicit function variable declaration for recursive anonymous functions. The recursive helper is therefore declared first and assigned afterward.
Unlike Python, Go does not have None, so nil is returned for empty subtrees.
Worked Examples
Example 1
Input:
preorder = [1,2,4,5,3,6,7]
postorder = [4,5,2,6,7,3,1]
Initial Call
| Variable | Value |
|---|---|
| Root | 1 |
| Left subtree root | 2 |
| Left root index in postorder | 2 |
| Left subtree size | 3 |
Tree so far:
1
Recursive ranges:
| Subtree | Preorder Range | Postorder Range |
|---|---|---|
| Left | [2,4,5] | [4,5,2] |
| Right | [3,6,7] | [6,7,3] |
Construct Left Subtree
Root becomes 2.
| Variable | Value |
|---|---|
| Root | 2 |
| Left subtree root | 4 |
| Left root index | 0 |
| Left subtree size | 1 |
Tree:
1
/
2
Subtrees:
- left child = 4
- right child = 5
Construct Right Subtree
Root becomes 3.
| Variable | Value |
|---|---|
| Root | 3 |
| Left subtree root | 6 |
| Left root index | 3 |
| Left subtree size | 1 |
Subtrees:
- left child = 6
- right child = 7
Final tree:
1
/ \
2 3
/ \ / \
4 5 6 7
Example 2
Input:
preorder = [1]
postorder = [1]
Initial call:
| Variable | Value |
|---|---|
| Root | 1 |
| Node count | 1 |
Since the subtree contains only one node, the recursion immediately returns the node.
Final tree:
1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each node is processed once |
| Space | O(n) | Hash map plus recursion stack |
The algorithm visits every node exactly once during recursive construction. Hash map lookups occur in constant time, so no additional traversal scanning is needed.
The recursion depth can reach O(n) in the worst case for a skewed tree. The hash map also stores one entry per node, resulting in linear auxiliary space usage.
Test Cases
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
# Example 1: full binary tree
root = Solution().constructFromPrePost(
[1,2,4,5,3,6,7],
[4,5,2,6,7,3,1]
)
assert level_order(root) == [1,2,3,4,5,6,7]
# Example 2: single node tree
root = Solution().constructFromPrePost(
[1],
[1]
)
assert level_order(root) == [1]
# Two-node tree
root = Solution().constructFromPrePost(
[1,2],
[2,1]
)
assert level_order(root)[0] == 1 # root exists
assert level_order(root)[1] == 2 # child attached correctly
# Left-skewed style structure
root = Solution().constructFromPrePost(
[1,2,3,4],
[4,3,2,1]
)
assert level_order(root)[0] == 1
# Balanced tree with three levels
root = Solution().constructFromPrePost(
[1,2,4,5,3,6,7],
[4,5,2,6,7,3,1]
)
assert root.left.val == 2
assert root.right.val == 3
# Tree with only left subtree
root = Solution().constructFromPrePost(
[1,2,3],
[3,2,1]
)
assert root.left is not None
# Verify leaf nodes
root = Solution().constructFromPrePost(
[1,2,4,5,3],
[4,5,2,3,1]
)
assert root.left.left.val == 4
assert root.left.right.val == 5
Test Summary
| Test | Why |
|---|---|
| Full balanced tree | Validates normal recursive subdivision |
| Single node | Validates smallest possible input |
| Two-node tree | Validates minimal recursive split |
| Skewed tree | Tests worst-case recursion depth |
| Three-level balanced tree | Confirms correct subtree partitioning |
| Tree with one subtree | Verifies ambiguous structure handling |
| Leaf validation | Ensures correct child attachment |
Edge Cases
Single Node Tree
When the input contains only one node, preorder and postorder are identical. A common bug is continuing recursion unnecessarily and accessing invalid indices such as pre_left + 1.
The implementation prevents this by checking:
if pre_left == pre_right:
return root
This immediately terminates recursion for leaf nodes.
Skewed Trees
A skewed tree occurs when every node has only one child. In such cases, preorder and postorder traversals do not uniquely determine whether children are left or right children.
The problem explicitly allows returning any valid tree. The implementation consistently constructs the child as part of the left subtree because it always treats the next preorder value as the left subtree root.
This guarantees a valid reconstruction.
Empty Recursive Ranges
During recursive subdivision, subtree ranges may become invalid:
pre_left > pre_right
Without handling this condition, recursion would attempt invalid array access.
The implementation safely returns None or nil for empty ranges:
if pre_left > pre_right:
return None
This correctly terminates recursion and attaches empty child pointers where appropriate.