Construct Binary Tree from Inorder and Postorder Traversal solution and explanation
Google
9 more videos on this problem
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - PythonNeetCodeIO · 14:31 · 42K views
Construct Binary Tree from Inorder and Postorder Traversal | LeetCode 106 | C++, Java, Python3Knowledge Center · 25:39 · 16K views
Construct Binary Tree from Inorder and Postorder Traversal | Leetcode 106 | codestorywithMIKcodestorywithMIK · 25:38 · 15K views
Leetcode - Construct Binary Tree from Inorder and Postorder Traversal (Python)Timothy H Chang · 11:22 · 4K views
[Java] Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal [Binary Tree #7]Eric Programming · 13:09 · 3K views
Construct Binary Tree from Inorder and Postorder Traversal | Leetcode 106 | Live coding session 🔥🔥🔥Coding Decoded · 10:14 · 646 views
106. Construct Binary Tree from Inorder and Postorder Traversal - JAVA (Detailed explanation)Sourin Majumdar · 23:00 · 476 views
106. Construct Binary Tree from Inorder and Postorder Traversal | LeetCode Daily | LeetCode POTDDeep Tech · 15:42 · 428 views
LeetCode 106 Construct Binary Tree from Inorder and Postorder TraversalJeevan Kumar - Cracckify · 7:58 · 339 views
L35. Construct the Binary Tree from Postorder and Inorder Traversal | C++ | Javatake U forward · 19:46 · 211K views
The problem
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] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree.
Approach overview
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.
Approach 1: Recursive Approach using HashMap
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def buildTree(self, inorder, postorder):
idx_map = {val: idx for idx, val in enumerate(inorder)}
self.post_idx = len(postorder) - 1
def helper(in_left, in_right):
if in_left > in_right:
return None
root_val = postorder[self.post_idx]
root = TreeNode(root_val)
self.post_idx -= 1
index = idx_map[root_val]
root.right = helper(index + 1, in_right)
root.left = helper(in_left, index - 1)
return root
return helper(0, len(inorder) - 1)import java.util.HashMap;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int post_idx;
private int[] postorder;
private HashMap<Integer, Integer> idx_map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
post_idx = postorder.length - 1;
int idx = 0;
for (int val : inorder)
idx_map.put(val, idx++);
return helper(0, inorder.length - 1);
}
private TreeNode helper(int in_left, int in_right) {
if (in_left > in_right)
return null;
int root_val = postorder[post_idx];
TreeNode root = new TreeNode(root_val);
post_idx--;
int index = idx_map.get(root_val);
root.right = helper(index + 1, in_right);
root.left = helper(in_left, index - 1);
return root;
}
}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.
Approach 2: Iterative Approach using 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.
function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var buildTree = function(inorder, postorder) {
if (!postorder.length) return null;
let root = new TreeNode(postorder[postorder.length - 1]);
let stack = [root];
let inorderIndex = inorder.length - 1;
for (let i = postorder.length - 2; i >= 0; i--) {
let node = stack[stack.length - 1];
if (node.val !== inorder[inorderIndex]) {
node.right = new TreeNode(postorder[i]);
stack.push(node.right);
} else {
while (stack.length && stack[stack.length - 1].val === inorder[inorderIndex]) {
node = stack.pop();
inorderIndex--;
}
node.left = new TreeNode(postorder[i]);
stack.push(node.left);
}
}
return root;
};public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
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;
}
}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.
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 3: Hash Table + Recursion
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:
- If
n leq 0, it means the subtree is empty, return a null node. - Otherwise, take out the last node
vof the post-order traversal, and then find the positionkofvin the in-order traversal using the hash tabled. Then the number of nodes in the left subtree isk - i, and the number of nodes in the right subtree isn - k + i - 1. - Recursively construct the left subtree
dfs(i, j, k - i)and the right subtreedfs(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.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map<int, int> d;
int n = inorder.size();
for (int i = 0; i < n; ++i) {
d[inorder[i]] = i;
}
function<TreeNode*(int, int, int)> dfs = [&](int i, int j, int n) -> TreeNode* {
if (n <= 0) {
return nullptr;
}
int v = postorder[j + n - 1];
int k = d[v];
auto l = dfs(i, j, k - i);
auto r = dfs(k + 1, j + k - i, n - k + i - 1);
return new TreeNode(v, l, r);
};
return dfs(0, 0, n);
}
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
const n = inorder.length;
const d: Record<number, number> = {};
for (let i = 0; i < n; i++) {
d[inorder[i]] = i;
}
const dfs = (i: number, j: number, n: number): TreeNode | null => {
if (n <= 0) {
return null;
}
const v = postorder[j + n - 1];
const k = d[v];
const l = dfs(i, j, k - i);
const r = dfs(k + 1, j + k - i, n - 1 - (k - i));
return new TreeNode(v, l, r);
};
return dfs(0, 0, n);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
d := map[int]int{}
for i, v := range inorder {
d[v] = i
}
var dfs func(i, j, n int) *TreeNode
dfs = func(i, j, n int) *TreeNode {
if n <= 0 {
return nil
}
v := postorder[j+n-1]
k := d[v]
l := dfs(i, j, k-i)
r := dfs(k+1, j+k-i, n-k+i-1)
return &TreeNode{v, l, r}
}
return dfs(0, 0, len(inorder))
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
impl Solution {
pub fn build_tree(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
let n = inorder.len();
let mut d: HashMap<i32, usize> = HashMap::new();
for i in 0..n {
d.insert(inorder[i], i);
}
fn dfs(
postorder: &[i32],
d: &HashMap<i32, usize>,
i: usize,
j: usize,
n: usize,
) -> Option<Rc<RefCell<TreeNode>>> {
if n <= 0 {
return None;
}
let val = postorder[j + n - 1];
let k = *d.get(&val).unwrap();
let left = dfs(postorder, d, i, j, k - i);
let right = dfs(postorder, d, k + 1, j + k - i, n - 1 - (k - i));
Some(Rc::new(RefCell::new(TreeNode { val, left, right })))
}
dfs(&postorder, &d, 0, 0, n)
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Construct Binary Tree from Inorder and Postorder Traversal easy or hard?
The problem is classified as Medium difficulty on most coding platforms. The logic becomes straightforward once you recognize that postorder's last element is the root and inorder defines subtree boundaries. Efficient solutions require understanding recursion, tree traversal patterns, and hash map optimization.
Construct Binary Tree from Inorder and Postorder Traversal Python/Java solution
In Python or Java, the standard implementation uses recursion with a HashMap (or dictionary) that maps node values to their positions in the inorder array. The algorithm processes the postorder list from the end, constructs the root, splits the inorder range, and recursively builds right and left subtrees.
How to solve Construct Binary Tree from Inorder and Postorder Traversal in O(n)?
Process the postorder array from the end because the last element represents the root. Use a HashMap to quickly locate that root in the inorder array, which divides the subtree ranges. Recursively build the right subtree first and then the left subtree while shrinking the inorder boundaries. Each element is processed once, producing O(n) time complexity.
What is the best approach for Construct Binary Tree from Inorder and Postorder Traversal?
The most efficient approach uses recursion with a HashMap to store inorder indices. The last element of the postorder array is always the root, and the inorder index splits the tree into left and right subtrees. Using a hash map avoids repeated searches in the inorder array, resulting in O(n) time complexity and O(n) space complexity.
Is Construct Binary Tree from Inorder and Postorder Traversal asked at Google/Amazon/Meta?
Binary tree reconstruction problems appear frequently in interviews at companies like Amazon, Google, Meta, and Microsoft. Variants include building a tree from preorder and inorder traversals or verifying traversal sequences. The problem tests understanding of tree traversal properties and divide-and-conquer recursion.
What data structure is used in Construct Binary Tree from Inorder and Postorder Traversal?
The main data structures are arrays for the traversal inputs, a hash map for fast index lookup in the inorder array, and a binary tree structure for the result. Some implementations also use a stack for an iterative solution that simulates recursion.
What is the time complexity of Construct Binary Tree from Inorder and Postorder Traversal?
The optimal solution runs in O(n) time where n is the number of nodes in the tree. Each node is created exactly once, and the HashMap allows constant-time lookup of the root index in the inorder array. Space complexity is O(n) due to recursion depth and the auxiliary map.