☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Construct the Binary Tree from Postorder and Inorder Traversal

Hard TUF ID 2781 A2ZBlind 75

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. Build the tree and return its root.

Constraints (LeetCode version): 1 ≤ n ≤ 3000, values in [-3000, 3000], all values unique, and the arrays are guaranteed to come from a real tree. The Java file also accepts empty arrays and returns null. The methods take inorder first, matching the LeetCode signature.

Example 1

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

        3
       / \
      9   20
         /  \
        15   7
answer = [3, 9, 20, null, null, 15, 7]   // 3 is last in postorder, so it is the root

Example 2

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

The key observation

Postorder visits the left subtree, then the right subtree, and only then the root. Inorder visits the left subtree, the root, then the right subtree:

postorder: [ left subtree (leftSize values) | right subtree | root ]
inorder:   [ left subtree (leftSize values) | root | right subtree ]

So the root is the last value of postorder. Locating that value in inorder splits everything else: the leftSize values before it form the left subtree, the values after it form the right subtree. In postorder, the left subtree is the first leftSize values of the range and the right subtree is everything between them and the root. Each piece is again an (inorder, postorder) pair of a smaller tree, so the same step applies recursively. Distinct values are what make the inorder lookup unambiguous.

Both methods work on index ranges instead of copied arrays: post[postStart..postEnd] is the current subtree’s postorder, and its inorder starts at in[inStart] with the same length.

Approach 1: Brute force, linear search for the root

Intuition. Implement the observation literally. At each call, take the last value of the postorder range as the root and scan the inorder range from its start until that value is found.

Algorithm.

  1. If the postorder range is empty (postStart > postEnd), return null.
  2. Create the root from post[postEnd].
  3. Scan in from inStart to find rootIndex, and let leftSize = rootIndex - inStart.
  4. Left child: postorder range postStart .. postStart + leftSize - 1, inorder starting at inStart.
  5. Right child: postorder range postStart + leftSize .. postEnd - 1, inorder starting at rootIndex + 1.
static TreeNode bruteForce(int[] inorder, int[] postorder) {
    return buildScan(postorder, 0, postorder.length - 1, inorder, 0);
}

// builds the tree whose postorder is post[postStart..postEnd] and whose inorder starts at in[inStart]
static TreeNode buildScan(int[] post, int postStart, int postEnd, int[] in, int inStart) {
    if (postStart > postEnd) return null;
    TreeNode root = new TreeNode(post[postEnd]);           // postorder always ends with the root
    int rootIndex = inStart;
    while (in[rootIndex] != root.val) rootIndex++;         // linear search: O(size of this subtree)
    int leftSize = rootIndex - inStart;
    root.left = buildScan(post, postStart, postStart + leftSize - 1, in, inStart);
    root.right = buildScan(post, postStart + leftSize, postEnd - 1, in, rootIndex + 1);
    return root;
}

Complexity. Time O(n^2) in the worst case. In a chain of left children, inorder equals postorder and each root is the last value of its inorder range, so the scans cost n + (n - 1) + ... + 1. A balanced tree costs O(n log n). Space O(n) for the nodes plus O(h) recursion depth.

Approach 2: Optimal, hash map for the root position

Intuition. Every value has exactly one inorder position, so precompute value → index in a hash map. Each root lookup is then O(1) and every node is built in constant time.

Algorithm.

  1. Fill inIndex with inorder[i] → i.
  2. Recurse as in Approach 1, but read rootIndex from the map.
static TreeNode optimal(int[] inorder, int[] postorder) {
    Map<Integer, Integer> inIndex = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) inIndex.put(inorder[i], i);
    return buildMap(postorder, 0, postorder.length - 1, 0, inIndex);
}

static TreeNode buildMap(int[] post, int postStart, int postEnd, int inStart, Map<Integer, Integer> inIndex) {
    if (postStart > postEnd) return null;
    TreeNode root = new TreeNode(post[postEnd]);
    int rootIndex = inIndex.get(root.val);
    int leftSize = rootIndex - inStart;
    root.left = buildMap(post, postStart, postStart + leftSize - 1, inStart, inIndex);
    root.right = buildMap(post, postStart + leftSize, postEnd - 1, rootIndex + 1, inIndex);
    return root;
}

Dry run on Example 1 (inIndex = {9→0, 3→1, 15→2, 20→3, 7→4}):

call (postStart, postEnd, inStart) root rootIndex leftSize left call right call
(0, 4, 0) 3 1 1 (0, 0, 0) (1, 3, 2)
(0, 0, 0) 9 0 0 (0, -1, 0) empty (0, -1, 1) empty
(1, 3, 2) 20 3 1 (1, 1, 2) (2, 2, 4)
(1, 1, 2) 15 2 0 empty empty
(2, 2, 4) 7 4 0 empty empty

The links are 3 → (9, 20) and 20 → (15, 7), the expected tree.

Complexity. Time O(n): building the map is O(n) and each node costs O(1). Space O(n) for the map and the nodes, plus O(h) recursion depth.

A common variant and its trap

Many solutions keep a single global index that walks backwards through postorder, taking the next root each time, instead of passing explicit postorder ranges. That works because reading postorder from the end gives root, right subtree, left subtree. The trap: such code must build the right child before the left child. Building the left child first consumes values that belong to the right subtree and produces a wrong tree without any error. The range-based version above has no ordering dependency, because every call is told exactly which slice of postorder it owns.

Edge cases and pitfalls

The tests run both methods on the example, a single node, an empty tree, left and right chains, a perfect tree, an uneven tree, a zig-zag, and a 3000-node random tree whose traversals are generated from the tree itself.