#106 Construct Binary Tree from Inorder and Postorder Traversal

frequently reported atWalmart Microsoft Amazon Google Bloomberg

the problem

In plain words

You get the inorder and the postorder traversal of a binary tree whose values are all different (the method takes inorder first). Rebuild the tree and return its root.

in inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

out [3,9,20,null,null,15,7]

in inorder = [-1], postorder = [-1]

out [-1]

1 ≤ n ≤ 3000
-3000 ≤ value ≤ 3000
Values are unique
Both arrays describe the same tree

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBuild a tree from traversals Divide and conquer

Postorder ends with the root: [left… | right… | root]. Read it from the back and you meet the root, then the whole right subtree, then the left — so build the right subtree first. Inorder still tells you which values go left and right.

solutions

From brute force to optimal

Take the root from the end of the postorder range, scan inorder to find it, split, recurse.

root = postorder[rootAt].
Scan inorder[lo..hi] for root → mid; rightSize = hi − mid.
Right subtree's root is at rootAt − 1; left subtree's root is at rootAt − 1 − rightSize.

timeO(n²) worst

Each of n roots scans up to n inorder slots on a skewed tree; O(n log n) when balanced.

spaceO(h)

Recursion stack; no array copies.

javajava.util.*

1class Solution {2    public TreeNode buildTree(int[] inorder, int[] postorder) {3        return build(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);4    }5 6    /** The subtree's values are inorder[lo..hi]; its root is postorder[rootAt] (postorder ends with the root). */7    private TreeNode build(int[] inorder, int lo, int hi, int[] postorder, int rootAt) {8        if (lo > hi) return null;9        TreeNode root = new TreeNode(postorder[rootAt]);10        int mid = lo;11        while (inorder[mid] != root.val) mid++;                 // O(n) scan for the root12        int rightSize = hi - mid;13        root.right = build(inorder, mid + 1, hi, postorder, rootAt - 1);14        root.left = build(inorder, lo, mid - 1, postorder, rootAt - 1 - rightSize);15        return root;16    }17}

Precompute every value's inorder position; keep one pointer that walks postorder from the end.

Map each inorder value to its index; next = n − 1.
build(lo, hi): root = postorder[next--]; mid = map.get(root).
Build the right side (mid + 1, hi) first, then the left side (lo, mid − 1).

timeO(n)

Each node is created once with an O(1) lookup.

spaceO(n)

The map, plus O(h) recursion.

javajava.util.*

1class Solution {2    private int next;                                    // next unused postorder position, moving LEFT3    private Map<Integer, Integer> indexOf;4 5    public TreeNode buildTree(int[] inorder, int[] postorder) {6        indexOf = new HashMap<>();7        for (int i = 0; i < inorder.length; i++) indexOf.put(inorder[i], i);   // O(1) root lookup8        next = postorder.length - 1;                     // postorder: the root comes LAST9        return build(postorder, 0, inorder.length - 1);10    }11 12    private TreeNode build(int[] postorder, int lo, int hi) {13        if (lo > hi) return null;14        TreeNode root = new TreeNode(postorder[next--]);15        int mid = indexOf.get(root.val);                 // inorder: left | root | right16        root.right = build(postorder, mid + 1, hi);      // build RIGHT first: reading backwards, it comes next17        root.left = build(postorder, lo, mid - 1);18        return root;19    }20}

in the room

How to say it in the interview

talk track

Draw postorder = [left… | right… | root] under inorder = [left… | root | right…].
Say the one change from LC 105: the next root comes from the END of postorder, so the right subtree is built first.

traps

Building the left subtree first while reading postorder backwards: the next values belong to the right subtree, so the tree comes out wrong.
Mixing up the parameters: LeetCode's method is buildTree(inorder, postorder) — inorder first.

what they ask next

Follow-ups

From preorder and postorder (LC 889)?

Not always unique: a node with one child could have it on either side, so LeetCode accepts any valid tree. preorder[i + 1] is the left child's root; find it in postorder to size the left part.

Why must values be unique?

With duplicates, the root's position in inorder is ambiguous, so the tree isn't determined.

before you submit

Edge cases to test

One node → that node.
Only left children: inorder equals postorder.
Only right children: inorder is postorder reversed.

practise next