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.Problem Overview: You are given two traversal arrays of the same binary tree: inorder and postorder. The goal is to reconstruct the original binary tree. The challenge is determining how to split the tree correctly using the ordering properties of both traversals.
Approach 1: Recursive Divide and Conquer with HashMap (O(n) time, O(n) space)
The key observation comes from traversal properties. In postorder, the last element is always the root of the current subtree. Once you identify the root, you locate its position inside the inorder array. Everything to the left of that index belongs to the left subtree, and everything to the right belongs to the right subtree. To avoid repeatedly scanning the inorder array, store each value's index in a HashMap for constant-time lookups.
The algorithm processes the postorder array from the end. Each recursive call creates a node, splits the inorder range, and recursively builds the right subtree first, then the left subtree. Building the right subtree first is necessary because postorder processes nodes as left → right → root, so when iterating backwards the order becomes root → right → left. Each node is created exactly once, producing O(n) time complexity with O(n) space for recursion and the hash map. This approach combines divide and conquer with efficient lookups using a hash table.
Approach 2: Iterative Construction using Stack (O(n) time, O(n) space)
An iterative strategy avoids recursion by simulating the construction process with a stack. Start from the last element of postorder, which is the root, and push it onto the stack. Traverse the postorder array backwards while tracking an index in the inorder array. The stack represents the path of nodes whose left child hasn't been attached yet.
If the top of the stack doesn't match the current inorder value, the next node becomes the right child of the stack's top node. If it matches, pop nodes from the stack until the values diverge; the next created node becomes the left child of the last popped node. This mirrors how inorder traversal signals that the right subtree has finished and the algorithm should move left. Each node is pushed and popped at most once, giving O(n) time complexity and O(n) auxiliary stack space. The approach is useful when you want to avoid deep recursion while working with binary tree construction problems.
Recommended for interviews: The recursive HashMap approach is the expected solution. It clearly demonstrates understanding of traversal properties and divide and conquer. Interviewers usually want to see the insight that the last element of postorder is the root and that a hash map reduces the lookup cost to O(1). The iterative stack version shows deeper mastery but is less commonly expected as the primary solution.
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.
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.
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.
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.
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.
JavaScript
C#
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.
The last node in the post-order traversal is the root node. We can find the position of the root node in the in-order traversal, and then recursively construct the left and right subtrees.
Specifically, we first use a hash table d to store the position of each node in the in-order traversal. Then we design a recursive function dfs(i, j, n), where i and j represent the starting positions of the in-order and post-order traversals, respectively, and n represents the number of nodes in the subtree. The function logic is as follows:
n leq 0, it means the subtree is empty, return a null node.v of the post-order traversal, and then find the position k of v in the in-order traversal using the hash table d. Then the number of nodes in the left subtree is k - i, and the number of nodes in the right subtree is n - k + i - 1.dfs(i, j, k - i) and the right subtree dfs(k + 1, j + k - i, n - k + i - 1), connect them to the root node, and finally return the root node.The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
| Approach | Complexity |
|---|---|
| Recursive Approach using HashMap | Time Complexity: O(n), where n is the number of nodes. Each node is visited once. |
| Iterative Approach using Stack | Time Complexity: O(n), where n is the number of nodes. Every element is seen once. |
| Hash Table + Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Divide and Conquer with HashMap | O(n) | O(n) | Best general solution. Clean recursion and constant-time inorder lookups. |
| Iterative Construction using Stack | O(n) | O(n) | Useful when avoiding recursion or when stack-based tree construction is preferred. |
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python • NeetCodeIO • 40,354 views views
Watch 9 more video solutions →Practice Construct Binary Tree from Inorder and Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCode