Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1] Output: [-1]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder and postorder consist of unique values.postorder also appears in inorder.inorder is guaranteed to be the inorder traversal of the tree.postorder is guaranteed to be the postorder traversal of the tree.In #106 Construct Binary Tree from Inorder and Postorder Traversal, the key observation is how each traversal reveals structural information about the tree. In postorder, the last element always represents the root of the current subtree. Once the root is identified, its position in the inorder traversal divides the array into left and right subtrees.
A common strategy is to build a hash map that stores the index of each value in the inorder array. This allows constant-time lookup when determining subtree boundaries. Using a divide and conquer approach, recursively construct the right and left subtrees by shrinking the valid index ranges in both traversals. Because postorder processes nodes as left → right → root, you typically build the right subtree first when iterating backward.
With the help of a hash map and recursion, the tree can be reconstructed efficiently in O(n) time while maintaining linear auxiliary space for recursion and indexing.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Recursive Divide and Conquer | O(n) | O(n) |
NeetCode
This approach uses recursion and a HashMap to efficiently construct the binary tree. The key insight is that the last element in the postorder array is the root node. This node's index in the inorder array can be found using a HashMap, allowing constant time access during recursive calls.
Time Complexity: O(n), where n is the number of nodes. Each node is visited once.
Space Complexity: O(n), where n is the number of nodes for storing the map and recursion stack.
1import java.util.HashMap;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10class Solution {
11 private int post_idx;
12 private int[] postorder;
13 private HashMap<Integer, Integer> idx_map = new HashMap<>();
14
15 public TreeNode buildTree(int[] inorder, int[] postorder) {
16 this.postorder = postorder;
17 post_idx = postorder.length - 1;
18
19 int idx = 0;
20 for (int val : inorder)
21 idx_map.put(val, idx++);
22
23 return helper(0, inorder.length - 1);
24 }
25
26 private TreeNode helper(int in_left, int in_right) {
27 if (in_left > in_right)
28 return null;
29
30 int root_val = postorder[post_idx];
31 TreeNode root = new TreeNode(root_val);
32 post_idx--;
33
34 int index = idx_map.get(root_val);
35 root.right = helper(index + 1, in_right);
36 root.left = helper(in_left, index - 1);
37
38 return root;
39 }
40}In this Java solution, a recursive helper function is used in conjunction with a HashMap to efficiently locate indices of given values. The hashmap helps in quick lookup of indices, speeding up the recursive construction.
This approach builds the tree using an iterative method with a stack. It tracks nodes that need a child and assigns them accordingly. It takes advantage of the tree properties in the postorder and inorder arrays for efficient traversal and node placement.
Time Complexity: O(n), where n is the number of nodes. Every element is seen once.
Space Complexity: O(n), where n is the number of nodes to account for the stack and tree storage.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode BuildTree(int[] inorder, int[] postorder) {
if (postorder.Length == 0) return null;
TreeNode root = new TreeNode(postorder[postorder.Length - 1]);
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
int inorderIndex = inorder.Length - 1;
for (int i = postorder.Length - 2; i >= 0; i--) {
TreeNode node = stack.Peek();
if (node.val != inorder[inorderIndex]) {
node.right = new TreeNode(postorder[i]);
stack.Push(node.right);
} else {
while (stack.Count > 0 && stack.Peek().val == inorder[inorderIndex]) {
node = stack.Pop();
inorderIndex--;
}
node.left = new TreeNode(postorder[i]);
stack.Push(node.left);
}
}
return root;
}
}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
A hash map stores the index of each value from the inorder traversal for constant-time lookup. Without it, finding the root index would take O(n) each time, increasing the total complexity to O(n^2). The hash map ensures the algorithm runs in linear time.
The main data structures used are arrays for the traversals, a hash map for quick index lookup in the inorder array, and recursion (or a stack implicitly) to rebuild the binary tree structure.
Yes, variations of this problem frequently appear in FAANG and other top tech company interviews. It tests understanding of tree traversals, recursion, and divide-and-conquer strategies, which are fundamental DSA concepts.
The optimal approach uses divide and conquer with a hash map. The last element of the postorder traversal identifies the root, and its index in the inorder traversal splits the tree into left and right subtrees. Recursively applying this idea rebuilds the entire tree efficiently.
This C# solution employs an iterative strategy using a stack to keep track of nodes waiting for children. It efficiently handles both left and right placements by ensuring stack-popped nodes are aligned with the inorder positions.