LeetCode 226 · Trees

Invert Binary Tree, explained with a picture

Flipping a mobile in a mirror.

EasyTrees
▶ Watch it step by step

The problem

Given a binary tree, invert it: swap every node’s left and right child, producing its mirror image.

Input:  [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]

Picture it

Picture a hanging mobile. Every hook (a node) has a left arm and a right arm. Holding the mobile up to a mirror means swapping the arms at every hook. We visit each hook, swap its two arms, then do the same for the hooks below.

How to recognise it

  • The input is a binary tree and the output is the same tree, changed in place.
  • The change is local: every node does the same small job (swap its two children) and needs nothing from its parent.
  • "Mirror", "flip" or "swap left and right" at every level is the classic wording.
  • Only up to 100 nodes, so any approach that touches each node once is enough. The point of the problem is the recursive shape, not speed.

Start with brute force

There is no slow brute force here, because every correct approach must visit every node. The naive version builds a brand-new mirrored copy and returns it, leaving the original untouched.

def mirror_copy(node):
    if not node:
        return None
    return Node(node.val, mirror_copy(node.right), mirror_copy(node.left))

It is O(n) time, which is already optimal, but it allocates n new nodes: O(n) extra memory on top of the O(h) recursion stack (h is the tree height). With 100 nodes that costs nothing, but the in-place version shows the pattern you will reuse on bigger trees.

From brute force to the idea

  1. Find the waste. The copy creates a new node for every old one, only to throw the old tree away. The old nodes already have the right values.
  2. Ask what one node must do. At a single node, the mirrored tree has the old right subtree on the left and the old left subtree on the right, each mirrored. So: mirror both children, then swap the two pointers.
  3. Trust the recursion. invert_tree(node.left) and invert_tree(node.right) fix everything below; the tuple assignment node.left, node.right = node.right, node.left swaps them in one step, with no temporary variable.
  4. Stop at empty spots. An empty child returns None and has nothing to swap.

This is the key idea: mirroring a tree means swapping the children at every node, and a depth-first search (DFS: follow one branch to the bottom before trying the next) visits each node once.

The shown code inverts the children first and swaps afterwards (post-order). Swapping first and then recursing (pre-order) works equally well: every node gets swapped exactly once either way.

The key idea

Recursion: invert the left subtree, invert the right subtree, swap them. Every node is visited once: O(n).

Python solution

def invert_tree(node):
    if not node:
        return None
    invert_tree(node.left)
    invert_tree(node.right)
    node.left, node.right = node.right, node.left   # swing the two arms
    return node

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (mirrored copy)O(n): one new node per old nodeO(n): n new nodes, plus O(h) recursion stack
In-place swap (shown code)O(n): each node is visited and swapped onceO(h): one stack frame per level, h = n for a chain

Edge cases

  • Empty tree (None): returns None.
  • Single node: returned unchanged.
  • Chain [1, 2, null, 3] (each node has only a left child): becomes a right-leaning chain [1, null, 2, null, 3].
  • Inverting twice gives back the original tree, a quick self-test.
  • Very deep tree: about 1,000 levels hits Python's default recursion limit. LeetCode caps this problem at 100 nodes, so it cannot happen here.

Common mistakes

  • Writing node.left = invert_tree(node.right) and then node.right = invert_tree(node.left): the second line reads the left child that was just overwritten.
  • Forgetting return node at the end, so the caller receives None instead of the root.
  • Swapping only the root's children and not recursing, which mirrors one level only.
Your turn: is the tree symmetric?

Decide whether a binary tree is a mirror image of itself (LeetCode 101): [1, 2, 2, 3, 4, 4, 3] is symmetric, [1, 2, 2, null, 3, null, 3] is not. Do it without changing the tree. Describe your approach, then write it if you like.

Compare with our answer

Compare the tree with its own mirror without building it. Walk two pointers at once: when one goes left, the other goes right. Two spots match if both are empty, or both hold the same value and their outer and inner children match.

def is_symmetric(root):
    def mirror(a, b):
        if not a or not b:
            return a is b                 # both empty?
        return (a.val == b.val
                and mirror(a.left, b.right)
                and mirror(a.right, b.left))
    return mirror(root, root)

Time O(n), space O(h). An empty tree counts as symmetric.

A strong answer mentions: pairing left with right (outer with outer, inner with inner), the both-empty base case, and that it reads the tree without modifying it.

Check what stuck

1. You must check whether two binary trees are mirror images of each other. Which approach fits best?

2. Why does the shown solution need only O(h) extra space?

3. A learner writes node.left = invert_tree(node.right) then node.right = invert_tree(node.left). Which tree still comes out right?

Score 60% or more and the lesson is marked complete.