226. Invert Binary TreeEasy

BFS DFS Recursive ★DFS Iterative Pitfalls

Invert Binary Tree

EasyBinary TreeBFSDFS·AmazonAppleMicrosoft

Given the rootof a binary tree, invert (mirror) the tree and return its root. Every node's left and right children are swapped at every level.

Example

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

Constraints

0 ≤ number of nodes ≤ 100 | -100 ≤ Node.val ≤ 100

1. Breadth-First Search O(n) · level-order

Intuition

Dequeue a node, swap its children, enqueue those children. Processes the tree row-by-row. The queue holds nodes whose children still need swapping.

STEP—

Press ▶ or step forward to begin.

✓

—

Space Play/Pause ·←→ Step ·F Fullscreen

Executing Code

class Solution:

    def invertTree(self, root):

        if not root:

            return None

        queue = deque([root])

        while queue:

            node = queue.popleft()

            node.left, node.right = node.right, node.left

            if node.left:  queue.append(node.left)

            if node.right: queue.append(node.right)

        return root

Time: O(n) | Space: O(n)

2. DFS — Recursive O(n) ★

Intuition

At every node: swap left and right, then recurse into the new left and new right. Base case: null — return immediately. The call stack drives the traversal.

Swap happens before recursing (pre-order) — children are swapped before going deeper.
The visualization shows each call frame on the call stack panel and the tree updating live as swaps occur.
Purple = current active node being processed. Green = fully inverted and returned.

STEP—

Press ▶ or step forward to begin.

✓

—

Space Play/Pause ·←→ Step ·F Fullscreen

Executing Code

class Solution:

    def invertTree(self, root):

        if not root:

            return None

        root.left, root.right = root.right, root.left

        self.invertTree(root.left)

        self.invertTree(root.right)

        return root

Time: O(n) | Space: O(n) call stack — O(log n) for balanced, O(n) for skewed

3. DFS — Iterative (Stack) O(n)

Intuition

Replace the call stack with an explicit stack — pop a node, swap its children, push them. Nearly identical to iterative BFS; the only difference is stack.pop() (LIFO) instead of queue.popleft() (FIFO), changing traversal order but not correctness.

The stack panel shows node values left-to-right (bottom→top). The rightmost = top = next to be popped.
Amber = in stack waiting. Purple = just popped. Green = swapped and done.

STEP—

Press ▶ or step forward to begin.

✓

—

Space Play/Pause ·←→ Step ·F Fullscreen

Executing Code

class Solution:

    def invertTree(self, root):

        if not root:

            return None

        stack = [root]

        while stack:

            node = stack.pop()

            node.left, node.right = node.right, node.left

            if node.left:  stack.append(node.left)

            if node.right: stack.append(node.right)

        return root

Time: O(n) | Space: O(n)

Common Pitfalls

Not handling null root: always return null immediately — accessing root.left on null causes NPE.
Wrong references after swap: after the swap, root.left points to what was root.right. Recursing on stale variable names uses incorrect references.
Pushing children before swapping (iterative): push children after the swap, otherwise the stack holds pre-swap references.
Confusing BFS vs DFS order: BFS uses popleft(), DFS uses pop(). Different traversal order, same correct result.

Discussion

…

Loading comments…

LeetMotion