DSA sheet · Trees · Construction pattern

Build Tree from Inorder & Postorder

This is the twin of the previous problem (Build Tree from Preorder & Inorder), and the teacher treats that video as a must-watch first. Inorder still does the splitting. The difference is that the root now comes from postorder, where the root is written last. That one fact causes two small changes: read postorder from the back, and build the right child before the left child. Understanding why the second change is needed is the real lesson of this video.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Build the tree with a hashmap (and right-first calls)
• Part B · Revision page

Part 0 · Before starting

Quick recap of the three orders

A subtree is a node plus everything below it. A window left..right is a range of indexes in the inorder list; each recursive call may only use the nodes in its window. left > right means the window is empty.

What we keep from the previous problem

• Find the root's index in inorder → everything before it is the left subtree, everything after it is the right subtree.
• Find that index in O(1) with a hashmap value → index built once from inorder (scanning would cost O(n) per node, O(n²) total).
• Pass index windows, not new lists. Stop when left > right. Return the root so the parent can link it.

The example tree for this page

        3
       / \
      9   20
     /   /  \
    4   15   7

inorder   = [4, 9, 3, 15, 20, 7]     (left, root, right)
postorder = [4, 9, 15, 7, 20, 3]     (left, right, root)

Part A · Build the tree with a hashmap (and right-first calls)

LeetCode 106 · Construct Binary Tree from Inorder and Postorder Traversal

1The question in simple words

You get inorder and postorder of the same binary tree. Rebuild the tree and return its root.

input:  inorder   = [4, 9, 3, 15, 20, 7]
        postorder = [4, 9, 15, 7, 20, 3]

output: the root of        3
                          / \
                         9   20
                        /   /  \
                       4   15   7

2What the constraints tell us

• 1 ≤ inorder.length ≤ 3000 → up to 3000 nodes, never empty. (Our code still returns None for empty lists.)
• postorder.length == inorder.length → both lists contain every node once.
• Values are small (−3000 to 3000), so a normal int is fine.
• All values are unique. The teacher stresses this again: to find a value's index (and to store it as a key in a map), each value must appear only once.
• n ≤ 3000 → O(n²) = 9 × 10⁶ would still pass, but with a hashmap we get O(n), so that's what we write.

3Intuition: how to think about it

The splitting picture is the same as before: point at the root in inorder, the left people are the left subtree, the right people are the right subtree.

The new question is only "where do I read the root from?" Postorder writes the root after both of its subtrees, so the last value of postorder is the root of the whole tree. Here that's 3.

Now read postorder backwards: 3, 20, 7, 15, 9, 4. That's root, then the right subtree's nodes, then the left subtree's nodes. Reading postorder from the back is like reading a preorder that visits right before left. That's the whole reason the right child must be built first.

postorder = [ 4   9 | 15   7  20 | 3 ]
              -----   ----------   ^
              left      right     root      (read it from the back:
                                             root, then right, then left)

4Building the logic from the example

Step 1 · The root is the last value of postorder

Postorder is "left, right, root", so the root of the whole tree is postorder[n - 1]. In preorder we started at index 0 and moved forward (+= 1). Here we start at the last index and move backward (-= 1). The teacher sets post_idx = n - 1, and since both lists have the same length, len(inorder) - 1 and len(postorder) - 1 are the same number.

Step 2 · Split with inorder (unchanged)

pos[3] = 2. Indexes 0..1 (4, 9) are the left subtree; indexes 3..5 (15, 20, 7) are the right subtree.

Step 3 · The next root belongs to the RIGHT side

After making 3, the pointer moves back one step to 20. In the preorder problem, the value after the root was the root of the left subtree. But look at the picture above: in postorder, the value just before the root is the root of the right subtree. 20 can't be the left child here; it's the right child.

So the pointer will hand out the right side's nodes first. If we call for the left child first, the left window (which holds only 4 and 9) would be handed 20. Therefore:

Step 4 · Base case and return (unchanged)

• Windows with left < right have several nodes; left == right has exactly one node, which we can still make.
• When the ends cross (left > right), there's nothing to build → return None. The caller is waiting for a node, and "no node" is None.
• After both children are attached, return root so the parent can attach this node.

The teacher's reminder: in tree or linked-list problems we usually stop when a node is None, but here we're creating nodes, not walking them, so the stop rule must use the indexes.

Step 5 · The hashmap and the shared pointer

• Build pos once from inorder. After that, inorder doesn't need to be passed to build; only postorder and the window are passed.
• The pointer must be shared by all calls, so in Python it lives on self as self.post_idx. A parameter would give each call its own copy, and the right call's progress would be lost when the left call starts.

5Approach steps

1. Fill pos[inorder[i]] = i for every index i.
2. Set post_idx = n - 1 (the last index of postorder).
3. Call build(0, n - 1) and return what it gives.
4. In build: if left > right → return None.
5. Make a node from postorder[post_idx], then post_idx -= 1.
6. mid = pos[node value].
7. Right first: root.right = build(mid + 1, right). Then root.left = build(left, mid - 1).
8. Return the node.

6Code (Python)

class Solution:
    def buildTree(self, inorder, postorder):
        self.pos = {}                              # value -> index in inorder
        for i in range(len(inorder)):
            self.pos[inorder[i]] = i
        self.post_idx = len(postorder) - 1         # start at the LAST value
        return self.build(postorder, 0, len(inorder) - 1)

    def build(self, postorder, left, right):
        if left > right:                           # window crossed: no node
            return None
        root = TreeNode(postorder[self.post_idx])
        self.post_idx -= 1                         # move BACKWARD

        mid = self.pos[root.val]
        root.right = self.build(postorder, mid + 1, right)   # right FIRST
        root.left = self.build(postorder, left, mid - 1)     # then left
        return root

7Code line by line

8Dry run: watch the windows split

inorder   = [4, 9, 3, 15, 20, 7]         pos = { 4:0, 9:1, 3:2, 15:3, 20:4, 7:5 }
postorder = [4, 9, 15, 7, 20, 3]         post_idx starts at 5

Boxes show the inorder list. Yellow = this window's root, plain = inside the window, grey = outside it.

Nodes were made in the order 3, 20, 7, 15, 9, 4, which is postorder read from the back. The right side of every node was finished before its left side, exactly as the pointer needed.

The teacher's picture: the nodes are created going down, but they are only joined into a tree as each call returns its root upward. 7 and 15 join 20, 20 joins 3, then 4 joins 9 and 9 joins 3.

9Complexity & remember

• Time O(n): one pass to fill the map, then one O(1) step per node.
• Space O(n): the recursion stack alone would be O(h), where h is the height (levels on the longest root-to-leaf path), about log n for a balanced tree. But the hashmap holds all n values, so total space is O(n). That map is the price we paid to make the time linear.

Part B · Revision page

def inorder_of(node):
    return inorder_of(node.left) + [node.val] + inorder_of(node.right) if node else []

def postorder_of(node):
    return postorder_of(node.left) + postorder_of(node.right) + [node.val] if node else []

ino = [4, 9, 3, 15, 20, 7]
post = [4, 9, 15, 7, 20, 3]
root = Solution().buildTree(ino, post)
print(root.val, root.left.val, root.right.val)               # 3 9 20
print(inorder_of(root) == ino, postorder_of(root) == post)   # True True
print(Solution().buildTree([1], [1]).val)                    # 1

Based on this video: Construct Binary Tree from Inorder and Postorder Traversal