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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def buildTree(self, inorder, postorder):
9 idx_map = {val: idx for idx, val in enumerate(inorder)}
10 self.post_idx = len(postorder) - 1
11
12 def helper(in_left, in_right):
13 if in_left > in_right:
14 return None
15
16 root_val = postorder[self.post_idx]
17 root = TreeNode(root_val)
18 self.post_idx -= 1
19
20 index = idx_map[root_val]
21 root.right = helper(index + 1, in_right)
22 root.left = helper(in_left, index - 1)
23
24 return root
25
26 return helper(0, len(inorder) - 1)This Python solution employs a recursive helper function to build the tree. The postorder index is decremented each time a new root is established, while the hashmap provides constant-time access to any given node's inorder index.
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.
1function TreeNode(val, left = null, right
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 JavaScript solution uses a stack to iteratively build the tree. It maintains nodes that need children and assigns nodes based on whether they are different from the current inorder node. Nodes are popped from the stack when they match inorder traversal to handle left children appropriately.