DSA sheet · Trees · Construction pattern

Build Tree from Preorder & Inorder

This video starts the construction pattern: instead of reading a tree that already exists, we are handed two lists of numbers and we have to rebuild the tree from them. The teacher shows that preorder tells us who the root is, and inorder tells us which nodes go left and which go right. Put those two facts together, repeat them for every smaller piece, and the whole tree falls out. The same idea is reused in the next two problems (inorder + postorder, preorder + postorder), so it is worth learning this one very well.

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 · Brute force: search the inorder list every time
• Part B · Optimal: a hashmap for inorder positions
• Part C · Revision page

Part 0 · Before starting

The node we will create

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

In this problem we don't get any nodes. We get plain numbers, and we make every node with TreeNode(value).

The three depth-first orders

A traversal is the order in which we visit the nodes. The three DFS orders differ only in when the root is written down:

A subtree is a node together with everything below it. "The left subtree of 3" means 3's left child and all of that child's descendants.

The example tree used all through this page:

        3
       / \
      9   20
     /   /  \
    4   15   7

preorder = [3, 9, 4, 20, 15, 7]     (root, then all of left, then all of right)
inorder  = [4, 9, 3, 15, 20, 7]     (all of left, then root, then all of right)

Why do we need TWO lists?

One list alone is not enough. Preorder [1, 2] could be either of these trees, because both write 1 first and then 2:

   1
  /
 2

   1
    \
     2

Their inorders are different though: [2, 1] for the first, [1, 2] for the second. So preorder gives us the root, and inorder settles the side. That is the whole reason the question gives us both.

Index ranges instead of new lists

We will often say "only look at the inorder list from index left to index right". That pair of numbers marks a window of the list. Every recursive call gets its own window, and the window is the set of nodes that call is allowed to use. When left > right, the window holds nothing.

Part A · Brute force: search the inorder list every time

LeetCode 105 · Construct Binary Tree from Preorder and Inorder Traversal

The teacher builds the full logic first and only then asks "how do we find the root inside inorder quickly?". Searching with a loop is the first idea, so we learn the whole recursion with that version. Part B then swaps the loop for a hashmap.

1The question in simple words

You get two lists, preorder and inorder, both made from the same binary tree. Build that tree and return its root node.

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

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

2What the constraints tell us

• 1 ≤ preorder.length ≤ 3000 → up to 3000 nodes. At least one node, so the tree is never empty (our code will still handle an empty list safely).
• inorder.length == preorder.length → obviously, since both lists list every node of one tree exactly once.
• Values from −3000 to 3000 → tiny numbers. A normal int holds them easily (in Java/C++ no need for long; in Python ints never overflow anyway).
• All values are unique. The teacher calls this very important. We are going to look up a value in inorder to find its position. If a value appeared twice, we wouldn't know which copy is the root. See the doubt in step 4.
• n ≤ 3000 → even O(n²) = 9 × 10⁶ steps is under the rough 10⁸ limit, so the brute force passes. It's just not the best we can do.

3Intuition: how to think about it

Think of the inorder list as a row of people standing left to right in the same left-to-right order as the tree. If you point at the root person, everybody standing to the root's left belongs to the left subtree, and everybody to the right belongs to the right subtree.

The only problem is that inorder doesn't tell us who the root is. That's where preorder comes in: preorder always writes the root first. So:

1. Preorder says "the root is 3".
2. Find 3 in inorder. Everything before it (4, 9) is the left subtree. Everything after it (15, 20, 7) is the right subtree.
3. Now solve the same puzzle again for the left group, and again for the right group.

inorder:  [ 4   9 | 3 | 15  20   7 ]
            -----   ^   ----------
            left   root    right

4Building the logic from the example

Step 1 · The root comes from preorder, not inorder

Inorder is "left, root, right", so the root sits somewhere in the middle and we can't say where. Preorder is "root, left, right", so its very first value is definitely the root. In our example that's 3.

Step 2 · Find the root inside inorder to split the nodes

3 is at index 2 in inorder. Since inorder writes the whole left subtree before the root, indices 0 and 1 (values 4 and 9) form the left subtree. We don't know yet how 4 and 9 are arranged, only that they're on the left. Indices 3 to 5 (15, 20, 7) form the right subtree.

Step 3 · Who is the root of the left group?

Look at preorder again: [3, 9, 4, 20, 15, 7]. After 3, preorder writes the whole left subtree before anything from the right. So the next value, 9, must be the root of the left subtree.

Now repeat step 2 for 9: find 9 in inorder (index 1). Whatever is before 9 is 9's left side, whatever is after is 9's right side.

Step 4 · One moving pointer on preorder

Preorder is used in a simple way: take the next value, make it a node, move on. The first call takes 3, the next call takes 9, the next takes 4, then 20, 15, 7. So we keep one counter, pre_idx, that starts at 0 and goes up by one every time a node is made.

This works only if we always build the left subtree before the right subtree. Preorder lists the whole left subtree before the right subtree, so the counter reaches the left nodes first. The teacher puts it as: make the root first, then root.left, then root.right.

Step 5 · Where does the recursion stop?

In most tree problems we stop when the node is None. Here there are no nodes yet; we are making them. We are only moving index numbers around, so the stopping rule must be about the indexes.

• left < right: the window has several nodes → keep building.
• left == right: the window has exactly one node (like 4 alone) → we can still make that one node.
• left > right: the two ends have crossed. Nothing is in between → return None.

Step 6 · Return the root so the parent can attach it

Each call makes one node, then fills its left and right by calling itself. When both children are done, it must return its node so the call above can store it. For example, the call for 4 gets None and None for its children, then returns 4. The call for 9 stores that 4 in 9.left, gets None on the right, and returns 9 to the call for 3, which stores it in 3.left.

The teacher's point: nodes are created on the way down, but they are linked together on the way back up, when each call returns its root.

Step 7 · Finding the root's position: the brute-force way

The simplest way to find the root inside inorder: walk the window from left to right until you see the value.

5Approach steps

1. Set a shared counter pre_idx = 0.
2. Call build(left=0, right=n-1).
3. In build: if left > right, return None.
4. Make a node from preorder[pre_idx], then add 1 to pre_idx.
5. Loop over inorder from left to right to find the index mid of that value.
6. Left child = build(left, mid - 1). Right child = build(mid + 1, right). Left first.
7. Return the node.

6Code (Python)

class Solution:
    def buildTree(self, preorder, inorder):
        self.pre_idx = 0                         # shared pointer into preorder
        return self.build(preorder, inorder, 0, len(inorder) - 1)

    def build(self, preorder, inorder, left, right):
        if left > right:                         # empty window
            return None
        root = TreeNode(preorder[self.pre_idx])  # next preorder value is the root
        self.pre_idx += 1

        mid = left                               # search the window for root.val
        while inorder[mid] != root.val:
            mid += 1

        root.left = self.build(preorder, inorder, left, mid - 1)
        root.right = self.build(preorder, inorder, mid + 1, right)
        return root

7Code line by line

8Dry run: count the searching work

The building steps are exactly the same as Part B (see the full dry run there). Here we only look at how many inorder cells each search reads, because that's the part the hashmap will remove.

Small here. But picture a tree that is a straight line going left (each node only has a left child). Preorder is [5, 4, 3, 2, 1], inorder is [1, 2, 3, 4, 5]. The root 5 is at the end of every window, so the searches read 5 + 4 + 3 + 2 + 1 cells. For n nodes that's about n²/2.

9Complexity & remember

• Time O(n²) in the worst case: for each of the n nodes we may scan up to n cells to find it. With n = 3000 that's 3 × 10³ × 3 × 10³ = 9 × 10⁶. The teacher notes this is below 10⁸, so it would not TLE, but it isn't the optimised answer.
• Space O(h): only the recursion stack, where h is the height of the tree (the number of levels on the longest root-to-leaf path). About log n for a balanced tree, n for a straight-line tree.

Part B · Optimal: a hashmap for inorder positions

The question, the constraints, the intuition, the base case and the order of the calls are all the same as Part A. Only step 7 changes: how we find the root's index in inorder.

1The question in simple words

Same as Part A: rebuild the tree from preorder and inorder, but now in O(n) time.

2What the constraints tell us

• Unique values → each value has exactly one index in inorder. That's what lets us store "value → index" in a dictionary. With duplicates, one key would need two indexes and the map wouldn't work.
• n up to 3000 → a dictionary of 3000 entries is cheap.

3Intuition: what's wasteful in Part A?

For 3 we scanned to find it. For 9 we scanned again. For 4 again, for 20 again… For every one of the n nodes we walk the list. But the inorder list never changes! So we can walk it once at the start and write down where every value lives, like a phone book. After that, "where is 20?" takes one look-up, O(1).

The data structure that answers "where is this value?" in O(1) is a hashmap (a Python dict).

inorder = [4, 9, 3, 15, 20, 7]
index:     0  1  2   3   4  5

pos = { 4: 0,  9: 1,  3: 2,  15: 3,  20: 4,  7: 5 }

4Building the logic: what changes

• Before building: loop over inorder once and fill pos[value] = index.
• Inside build: replace the search loop with mid = pos[root.val].
• The inorder list is no longer passed around. We only needed it to find positions, and the map already has them all. So build only needs preorder, left and right.

5Approach steps

1. Build pos: for each index i in inorder, pos[inorder[i]] = i.
2. Set pre_idx = 0 and call build(0, n - 1).
3. In build: if left > right → return None.
4. Make the node from preorder[pre_idx]; pre_idx += 1.
5. mid = pos[node value].
6. root.left = build(left, mid - 1), then root.right = build(mid + 1, right).
7. Return root.

6Code (Python)

class Solution:
    def buildTree(self, preorder, inorder):
        self.pos = {}                            # value -> index in inorder
        for i in range(len(inorder)):
            self.pos[inorder[i]] = i
        self.pre_idx = 0                         # shared pointer into preorder
        return self.build(preorder, 0, len(inorder) - 1)

    def build(self, preorder, left, right):
        if left > right:                         # window crossed: no node
            return None
        root = TreeNode(preorder[self.pre_idx])
        self.pre_idx += 1

        mid = self.pos[root.val]                 # O(1) instead of a scan
        root.left = self.build(preorder, left, mid - 1)
        root.right = self.build(preorder, mid + 1, right)
        return root

7Code line by line

8Dry run: watch the windows split

preorder = [3, 9, 4, 20, 15, 7]          pos = { 4:0, 9:1, 3:2, 15:3, 20:4, 7:5 }
inorder  = [4, 9, 3, 15, 20, 7]

In the boxes below, the yellow cell is the root of the window, plain cells are inside the window, and grey cells are outside it (this call may not touch them).

Notice how pre_idx moved 0, 1, 2, 3, 4, 5 in order, and the nodes were made in the order 3, 9, 4, 20, 15, 7, exactly the preorder list. That only happens because the left call always runs before the right call.

Newest call on top (red). When the call for 4 leaves the stack, 4 gets linked under 9. When 9 leaves, 9 gets linked under 3. The tree is joined from the bottom up.

result:     3
           / \
          9   20
         /   /  \
        4   15   7

9Complexity & remember

• Time O(n): one pass to fill the map, then each node is made once and its position is found in O(1). This is linear because of the hashmap; without it we're back to O(n²).
• Space O(n): the recursion stack alone is O(h) (one call per level on the current path; about log n when balanced). But the map stores all n values, and n ≥ h, so overall space is O(n). The teacher's way to say it: we spent O(n) extra space to bring the time down from n² to n.

Part C · Revision page

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

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

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

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