DSA sheet · Trees · Construction & serialization pattern

Invert Binary Tree

This is the first problem of a new pattern in the sheet: construction / serialization, where we build, rebuild or reshape a tree. Inverting is the gentlest start. We don't make new nodes, we just swap the left and right child at every node, and the tree becomes its own mirror image. The teacher also uses this video to show how to think your way to code: write the part you understand, then let the dry run tell you what's missing. She solves it with DFS (her favourite here), then BFS.

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

• Part 0 · What you must know before starting
• Part A · Invert Binary Tree with DFS
• Part B · Invert Binary Tree with BFS
• Part C · Revision page

Part 0 · Before starting

• Mirror image: what you'd see if you held the tree up to a mirror. Everything on the left appears on the right, and everything on the right appears on the left. This holds at every level, not just at the top.
• Height (h): the number of levels. Balanced → about log n. Skewed (a straight line) → n.
• Width (w): the largest number of nodes on any single level. In a full tree, the bottom level is the widest, with about n/2 nodes.
• Swapping with a temp variable: to swap a and b, you need a third box. Otherwise the first assignment wipes out one value.
  the classic swap

  temp = a      # keep a safe
  a = b         # now a and b are both the old b
  b = temp      # put the old a into b

  Python can also do a, b = b, a in one line. It does the same thing safely.

Part A · Invert Binary Tree with DFS

LeetCode 226

1The question in simple words

Given the root of a binary tree, turn it into its mirror image and return the root.

        4
      /   \
     2     7
    / \   / \
   1   3 6   9

        4
      /   \
     7     2
    / \   / \
   9   6 3   1

The root 4 stays where it is. 2 was the left child and is now the right child. 7 was the right child and is now the left child. And below them, 1 and 3 also swapped, and so did 6 and 9.

2What the constraints tell us

• Nodes: 0 to 100 → the tree can be empty, so we need a base case for None.
  • The teacher repeats her rule: in DFS you always need a base case anyway, because the recursion will reach None children sooner or later.
  • In BFS you need it only if the tree can be empty. With at least one node, the root goes into the queue and the loop ends by itself. Here 0 is allowed, so BFS needs it too.
• Values: −100 to 100. We don't even do maths on them, we only move nodes around. An int can hold up to about 10⁹, so nothing to worry about.
• n ≤ 100 is tiny. Any reasonable solution is fast.

3Intuition: a swap at every node

Stand on a node. You can see its left child and its right child. Swap them, meaning the whole branches, not just the numbers. Then walk into each child and do the same thing there. When every node has swapped its two children, the whole tree is mirrored.

4Building the code step by step (the teacher's way)

Her tip: don't try to write the whole code in one go. Write the parts you understand. Later, when you dry-run it, you'll see if a line needs to move, or if a variable or line is missing. That's exactly what happens here.

Step 1: the base case, and what should it return?

We know DFS needs "if the node is None, return…" but return what? Think about what the parent wants from its children. Does the parent need some number back, like a height or a sum? No. The parent just wants its two children swapped. So at first she writes a plain return.

Later, when she runs the Java code, it fails to compile. The function's return type is TreeNode, so it must return something. She changes it to return null. It also covers the case where the whole tree is empty: the answer for an empty tree is an empty tree.

Step 2: swap the two children of the current node

We're standing on the root, so we can reach root.left and root.right. Swap them with a temp variable, like swapping two numbers:

1. temp = root.left: keep the left branch (2 with 1, 3) safe.
2. root.left = root.right: now the left link points at 7.
3. root.right = temp: the right link gets the saved 2-branch.

The teacher draws the tree between lines 2 and 3. It's a great way to see why the temp is needed:

        4
      /   \
     7     7      ← same 7-branch twice!
    / \   / \
   6   9 6   9

  temp → 2 (1, 3)  ← still safe

        4
      /   \
     7     2
    / \   / \
   6   9 1   3

Half-way through, both links point at the 7-branch, and the 2-branch survives only because temp holds it. Without the temp, the 2-branch would be lost forever.

Step 3: the root is right now, but the lower levels aren't

Look at the "after line 3" picture. 4, 7 and 2 are in the right places, but under 7 we have 6, 9, and the mirror needs 9, 6. Under 2 we have 1, 3 instead of 3, 1. So we repeat the same job for each child: call the same function on root.left and on root.right.

• Call on root.left (that's now the 7): it swaps 6 and 9 → 7 → (9, 6).
• Call on root.right (that's now the 2): it swaps 1 and 3 → 2 → (3, 1).

Step 4: what to return at the end?

The question wants the root of the inverted tree back, so the last line is return root.

5Approach steps

1. If the node is None → return None.
2. Swap its left and right children (temp variable).
3. Invert the left child's subtree, then the right child's subtree (recursively).
4. Return the node.

6Code (Python)

class Solution:
    def invertTree(self, root):
        if root is None:              # empty spot: nothing to swap
            return None
        temp = root.left              # keep the left branch safe
        root.left = root.right        # right branch moves to the left
        root.right = temp             # old left branch moves to the right
        self.invertTree(root.left)    # now mirror everything below, left...
        self.invertTree(root.right)   # ...and right
        return root                   # the caller wants the root back

class Solution:
    def invertTree(self, root):
        if root is None:
            return None
        # invert both children, then attach them on the opposite sides
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

The short version uses the return values: "the inverted right branch becomes my left, the inverted left branch becomes my right". Python evaluates both calls before assigning, so no temp is needed.

7Code line by line

8Dry run using the call stack

Tree 4 → (2 → 1, 3), (7 → 6, 9). "N" = None.

1. inv(4): swap → 4's left is 7, right is 2. Call inv(4.left) = inv(7). inv(4) waits.
2. inv(7): swap 6 and 9 → 7 → (9, 6). Call inv(9).
3. inv(9): a leaf. Swap None with None (no change). inv(N) → None, inv(N) → None. Return 9.
4. Back in inv(7): call inv(6), also a leaf → nothing changes → return 6. inv(7) returns 7 and leaves the stack.
5. Back in inv(4): call inv(4.right) = inv(2). Swap 1 and 3 → 2 → (3, 1).
6. inv(3) and inv(1) are leaves → nothing changes. inv(2) returns 2.
7. inv(4) returns 4. The tree is now 4 → (7 → 9, 6), (2 → 3, 1). ✓ That's the mirror.

      4
    /   \
   7     2
  / \   / \
 6   9 1   3

      4
    /   \
   7     2
  / \   / \
 9   6 1   3

      4
    /   \
   7     2
  / \   / \
 9   6 3   1

9Complexity & remember

• Time O(n): every node is visited once and does one swap. With n ≤ 100, that's about 100 steps, very fast.
• Space O(h): the call stack holds one call per level of the current path. Balanced → O(log n) (the teacher's figure). Skewed → O(n).

Part B · Invert Binary Tree with BFS

Same question and the same swap. Only the order we visit nodes changes: level by level with a queue, the way we did level order traversal before.

1Intuition

Put 4 in the queue. When we pop 4, we don't need its value for anything. We just swap its two children, exactly as in DFS. Then we push those children (now 7, 2) so that later we pop them and swap their children. Every node is popped once and swapped once.

• In DFS, the recursive calls on root.left and root.right take us to the next nodes.
• In BFS, pushing the children into the queue does that job.

2Constraints for BFS

Zero nodes is allowed. If the root is None, we must return None before we start, or we'd pop None and crash on None.left.

3Approach steps

1. If root is None → return None.
2. Queue starts with the root.
3. While the queue isn't empty: pop a node and swap its left and right children.
4. Push the children that exist (left, then right).
5. When the queue is empty → return root.

4Code (Python)

from collections import deque

class Solution:
    def invertTree(self, root):
        if root is None:                  # 0 nodes is allowed
            return None
        queue = deque([root])
        while queue:
            node = queue.popleft()
            temp = node.left              # same swap as DFS
            node.left = node.right
            node.right = temp
            if node.left:                 # line up the next level
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

5Code line by line

6Dry run: watch the queue

Order of swaps: 4, 7, 2, then the leaves. That's level by level. DFS swapped in the order 4, 7, 9, 6, 2, 3, 1. Different order, same final tree.

7Complexity & DFS vs BFS

• Time O(n): every node is popped once, and no node is repeated.
• Space O(w), the maximum width, instead of the height. The queue holds about one level at a time. In the example: level 0 has 1 node, level 1 has 2, level 2 has 4. The widest level wins. For a full tree that bottom level has about n/2 nodes, so O(n).

Both are efficient. The teacher still prefers DFS for inverting trees: it's shorter, and the stack only grows with the height, not the width.

Part C · Revision page

def level_order(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val)
            q += [n.left, n.right]
    return out

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
s = Solution()
print(level_order(s.invertTree(root)))                        # [4, 7, 2, 9, 6, 3, 1]
print(level_order(s.invertTree(TreeNode(2, TreeNode(1), TreeNode(3)))))   # [2, 3, 1]
print(s.invertTree(None))                                     # None

Based on this video: Invert Binary Tree | DFS & BFS