☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Construct a BT from Postorder and Inorder

Hard TUF ID 109 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given two integer arrays, inorder and postorder, which are the inorder and postorder traversals of the same binary tree. All values are distinct. Rebuild the tree and return its root.

Recall the two orders: inorder lists left subtree, node, right subtree; postorder lists left subtree, right subtree, node.

Constraints (LeetCode 106): 1 ≤ n ≤ 3000, values in [-3000, 3000], all distinct, and the input is guaranteed to be valid. The Java file also accepts n = 0 and returns null.

Example 1

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

answer:     3
           / \
          9   20
             /  \
            15   7

Postorder ends with 3, so 3 is the root; in inorder, 9 is to its left and 15, 20, 7 to its right.

Example 2

inorder = [-1], postorder = [-1]
answer  = a single node -1

Why both arrays are needed. Postorder alone is ambiguous: [1, 2] could be root 2 with left child 1 or root 2 with right child 1. Inorder tells them apart ([1, 2] versus [2, 1]). And distinct values matter: with duplicates the root’s position inside inorder is not unique, and different trees can share both traversals.

Approach 1: Recursion with a linear search for the root

Intuition. Two facts do all the work.

  1. The last element of a postorder sequence is the root, because postorder emits a node after both its subtrees.
  2. In the inorder sequence, the root sits between its left subtree and its right subtree. If the root is at index k of the current inorder range [inLo, inHi], the left subtree consists of the leftSize = k - inLo values before it, and the right subtree of the values after it.

Postorder lays out the same subtree as “left part, right part, root”. The left subtree has leftSize nodes, so inside the current postorder range [postLo, postHi] it occupies the first leftSize positions, the right subtree occupies the positions after that up to postHi - 1, and postHi holds the root. Now both subtrees are described by an inorder range and a postorder range of the same length, which is exactly the original problem on fewer nodes, so we recurse.

In this first version we find k by scanning the inorder range from the left.

Algorithm.

  1. If the inorder range is empty, return null.
  2. Create the root from post[postHi].
  3. Scan in[inLo..inHi] for the root value; call its index k. Let leftSize = k - inLo.
  4. Build the left child from in[inLo..k-1] and post[postLo..postLo+leftSize-1].
  5. Build the right child from in[k+1..inHi] and post[postLo+leftSize..postHi-1].
  6. Return the root.
static TreeNode bruteForce(int[] inorder, int[] postorder) {
    return buildScan(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}

static TreeNode buildScan(int[] in, int inLo, int inHi, int[] post, int postLo, int postHi) {
    if (inLo > inHi) return null;
    TreeNode root = new TreeNode(post[postHi]);          // postorder ends with the root
    int k = inLo;
    while (in[k] != root.val) k++;                       // root splits inorder into left | root | right
    int leftSize = k - inLo;
    root.left = buildScan(in, inLo, k - 1, post, postLo, postLo + leftSize - 1);
    root.right = buildScan(in, k + 1, inHi, post, postLo + leftSize, postHi - 1);
    return root;
}

Complexity. Time O(n^2) in the worst case. For a left chain, the root is always the last element of its inorder range, so the scans cost n + (n - 1) + ... + 1. For a balanced tree it is O(n log n). Space O(h) for the recursion, plus the O(n) nodes of the result.

Approach 2: Optimal, recursion with a hash map of inorder positions

Intuition. The only slow step is locating the root in inorder. Values are distinct, so we can precompute a map from value to inorder index once, in O(n). Each lookup is then O(1) on average, and the recursion does constant work per node. The range arithmetic is unchanged; the inorder array itself is no longer needed inside the recursion, only the map.

Algorithm.

  1. Build pos mapping each value to its index in inorder.
  2. Run the same recursion as Approach 1, replacing the scan by k = pos.get(rootValue).
static TreeNode optimal(int[] inorder, int[] postorder) {
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
    return buildMap(0, inorder.length - 1, postorder, 0, postorder.length - 1, pos);
}

static TreeNode buildMap(int inLo, int inHi, int[] post, int postLo, int postHi, Map<Integer, Integer> pos) {
    if (inLo > inHi) return null;
    TreeNode root = new TreeNode(post[postHi]);
    int k = pos.get(root.val);                           // O(1) instead of a scan
    int leftSize = k - inLo;
    root.left = buildMap(inLo, k - 1, post, postLo, postLo + leftSize - 1, pos);
    root.right = buildMap(k + 1, inHi, post, postLo + leftSize, postHi - 1, pos);
    return root;
}

Dry run on Example 1, with pos = {9:0, 3:1, 15:2, 20:3, 7:4}:

call inorder range postorder range root k leftSize
whole tree 0..4 0..4 post[4] = 3 1 1
left of 3 0..0 0..0 post[0] = 9 0 0
right of 3 2..4 1..3 post[3] = 20 3 1
left of 20 2..2 1..1 post[1] = 15 2 0
right of 20 4..4 2..2 post[2] = 7 4 0

The calls on node 9, 15 and 7 then receive empty ranges for their children and return null, giving the tree from Example 1.

Complexity. Time O(n): one pass to fill the map and constant work per node in the recursion. Space O(n) for the map plus O(h) for the recursion.

A common variant. Instead of passing a postorder range, keep a single index that starts at the end of postorder and moves left every time a node is created. Reading postorder backwards gives root, right subtree, left subtree, so with this variant you must build the right child before the left child. It has the same complexity and fewer parameters, but the hidden ordering requirement is an easy source of bugs, which is why the explicit ranges are used above.

Edge cases and pitfalls