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: Given two arrays representing the inorder and postorder traversal of a binary tree, reconstruct the original tree. Every value is unique, so the tree structure can be determined by splitting the traversals correctly.
Approach 1: Recursive Divide and Conquer (Naive) (Time: O(n^2), Space: O(n))
The last element in postorder is always the root of the current subtree. Find that value in the inorder array to split the tree into left and right subtrees. Recursively repeat the process for each side. The inefficiency comes from scanning the inorder array every time you look up the root index, which can take O(n) per recursive call. This approach demonstrates the core divide-and-conquer idea but becomes slow for large trees.
Approach 2: Recursive Approach using HashMap (Time: O(n), Space: O(n))
Store each value's index from the inorder array in a hash map for constant-time lookup. Start from the last element of postorder to identify the root. Use the index from the map to determine how many nodes belong to the left and right subtrees. Recursively build the right subtree first, then the left subtree, because postorder processes nodes in left-right-root order. Each node is processed once and each lookup is O(1), giving linear time complexity. This method combines recursion with a hash table and standard divide and conquer tree construction.
Approach 3: Iterative Approach using Stack (Time: O(n), Space: O(n))
An iterative method simulates the recursive construction using a stack. Traverse the postorder array from the end while tracking the inorder pointer. Each new value becomes either the right child of the current node or the left child of the last node whose value matches the inorder pointer. The stack keeps track of nodes whose left subtree has not been assigned yet. This approach avoids recursion and can be easier to control in languages where recursion depth is limited. It still processes each node once and relies on properties of binary tree traversals.
Recommended for interviews: The recursive HashMap approach is the expected solution. Interviewers want to see that you recognize the root position in postorder and use a hash map to avoid repeated scans of the inorder array. Showing the naive version first demonstrates understanding of the traversal relationship, but optimizing it to O(n) with constant-time index lookups shows strong problem-solving skills.
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.
Java
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.
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Divide and Conquer (No Map) | O(n^2) | O(n) | Useful for understanding traversal relationships before optimization |
| Recursive with HashMap | O(n) | O(n) | Best general solution and most common interview expectation |
| Iterative Stack Simulation | O(n) | O(n) | When avoiding recursion or stack depth limits |
Construct Binary Tree from Inorder and Preorder Traversal - Leetcode 105 - Python • NeetCode • 307,238 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