LeetCode #226 Easy

Invert Binary Tree

Mirror a binary tree: swap every node's left and right children.

treedfsrecursion

02

Intuition

💡

Writing node.left = invert(node.right) then node.right = invert(node.left) looks fine but is not: the first line overwrites node.left before the second line can read its original value, so the whole left subtree is silently lost. Swap the two child references simultaneously, with a temp variable or tuple assignment, and only then recurse into the (now swapped) children. The invariant is simple: after visiting a node, its left and right pointers must already point at each other's old subtrees before you descend.

03

Approach

1

Base case

An empty node has nothing to mirror -- return None immediately.

2

Swap before recursing

temp = node.left; node.left = node.right; node.right = temp. Do this in one atomic step so neither assignment clobbers data the other still needs.

3

Recurse into both sides

Call invert on node.left and node.right (which are now swapped) so the mirroring applies at every depth, not just the top.

04

Solution & live demo

python

▶1class Solution:
▶2    def invertTree(self, root):
▶3        if not root:
▶4            return None
▶5        root.left, root.right = root.right, root.left
▶6        self.invertTree(root.left)
▶7        self.invertTree(root.right)
▶8        return root

05

Edge cases

Empty tree

Return None right away.

Single node

Swap of two Nones is a no-op; returns the same node.

Only one child present

That child moves to the other side; the swap still works since the missing side is just None.

Already symmetric tree

Still fully swapped at every node -- symmetry does not mean invert is a no-op unless every value repeats mirrored.

06

Complexity

Time

O(n)

Space

O(h)

Every node visited once; recursion depth is the tree height.