Invert Binary Tree

Problem

Given the root of a binary tree, invert the tree, and return its root.

Examples

The brute-force approach

There's no meaningfully 'worse' approach here, the problem requires touching every node at least once, so O(n) is the floor. The interesting question is *which* traversal to use: recursive DFS, iterative DFS, or BFS.

# Iterative BFS (level-order), intuitive but uses a queue
from collections import deque

queue = deque([root])
while queue:
    node = queue.popleft()
    if node:
        node.left, node.right = node.right, node.left    # swap
        queue.append(node.left)
        queue.append(node.right)

This is already O(n) time and O(n) space. The recursive approach below achieves the same complexity with less code, a good opportunity to practice thinking recursively.

Spotting the pattern

This is a Tree Traversal problem. The key question to ask yourself:

Can I swap this node's children and then let recursion handle each subtree?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.