Construct Binary Tree from Inorder and Postorder Traversal

MediumTrees · DFS · Divide & Conquer🧩 Tree DFS LeetCode #106 ↗Updated Oct 30, 2026

Problem

You are given two arrays describing the same binary tree with distinct values: inorder (left, node, right) and postorder (left, right, node). Rebuild the tree and return its root.

Inputinorder = [9,3,15,20,7], postorder = [9,15,7,20,3]Output[3,9,20,null,null,15,7]

Inputinorder = [-1], postorder = [-1]Output[-1]

1 ≤ n ≤ 3000 · -3000 ≤ values ≤ 3000 · all values distinct · both arrays describe the same tree

Try it yourself

Java

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The last postorder value is the root; its position in inorder splits everything into left and right subtrees. Reading postorder backwards gives root, then the whole right subtree, then the left — so build right before left.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceRecursive Split with Linear Search

Time O(n²)Space O(h)

For the inorder range [lo, hi], the root is the next value taken from the back of postorder. Scan the range to find it at index m; build the right subtree from [m+1, hi] first (it precedes the root in postorder), then the left from [lo, m-1].

Java

private int post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    post = postorder.length - 1;
    return build(inorder, postorder, 0, inorder.length - 1);
}
private TreeNode build(int[] in, int[] postorder, int lo, int hi) {
    if (lo > hi) return null;
    TreeNode root = new TreeNode(postorder[post--]);
    int m = lo;
    while (in[m] != root.val) m++; // linear search for the root
    root.right = build(in, postorder, m + 1, hi);
    root.left = build(in, postorder, lo, m - 1);
    return root;
}

Correct and short, but the scan makes skewed trees quadratic.

BetterRecursive Split with Index Map

Time O(n)Space O(n)

Same recursion, but precompute value → inorder index in a HashMap (values are distinct), so each split is an O(1) lookup. Every node is created once with constant extra work.

Java

private int post;
private Map<Integer, Integer> pos;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    post = postorder.length - 1;
    pos = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
    return build(postorder, 0, inorder.length - 1);
}
private TreeNode build(int[] postorder, int lo, int hi) {
    if (lo > hi) return null;
    TreeNode root = new TreeNode(postorder[post--]);
    int m = pos.get(root.val); // O(1) split point
    root.right = build(postorder, m + 1, hi);
    root.left = build(postorder, lo, m - 1);
    return root;
}

Linear time; the textbook answer, at the cost of an O(n) map.

OptimalBoundary-Value Recursion (No Map)

Time O(n)Space O(h)

Walk both arrays from the end. A subtree is described by a stop value (its parent bound): keep building while inorder[in] hasn't reached the stop. A node's right subtree stops at the node itself; its left subtree inherits the parent's stop. Hitting the stop consumes it and returns null.

Java

private int post, in;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    post = postorder.length - 1;
    in = inorder.length - 1;
    return build(inorder, postorder, null);
}
private TreeNode build(int[] inorder, int[] postorder, Integer stop) {
    if (post < 0) return null;
    if (stop != null && inorder[in] == stop) { // subtree finished
        in--;
        return null;
    }
    TreeNode root = new TreeNode(postorder[post--]);
    root.right = build(inorder, postorder, root.val); // ends at root in inorder
    root.left = build(inorder, postorder, stop);      // ends at parent bound
    return root;
}

Linear with only the recursion stack — no map, no index ranges.

Pro tip

Mirror image of the preorder + inorder version (105): there you read both arrays forwards and build left first.

At a glance

Level	Approach	Time	Space
Brute Force	Recursive Split with Linear Search	`O(n²)`	`O(h)`
Better	Recursive Split with Index Map	`O(n)`	`O(n)`
Optimal	Boundary-Value Recursion (No Map)	`O(n)`	`O(h)`

Common pitfalls

Building the left subtree first while consuming postorder from the back — values land in the wrong subtree.
Using the shared postorder pointer in a non-recursive order (e.g. computing both ranges up front).
Assuming the trick works with duplicate values — the inorder split becomes ambiguous.

Interview tips

State the two facts: postorder's last = root, inorder index splits the subtrees.
Explain why the right subtree must be built first when reading postorder backwards.
Mention the map-free boundary version as the space follow-up.

Pattern

Traversal reconstruction (divide & conquer) → one traversal gives the root, inorder tells you how to split.

My notes saved in this browser