Invert Binary Tree (LeetCode 226): Swap Children Everywhere

Mirror a binary tree: every node's left and right children trade places. The famous one-liner hides a useful habit, which is stating the traversal you chose and why.

Recursive DFS

def invertTree(root):
    if root is None:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

Every node is touched once, so time is O(n). Space is O(h) for the call stack, where h is the tree height (O(n) for a skewed tree).

Iterative BFS

from collections import deque

def invertTree(root):
    q = deque([root] if root else [])
    while q:
        node = q.popleft()
        node.left, node.right = node.right, node.left
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return root

Swapping before or after visiting the children both work, because each node is swapped exactly once.

Interview notes

• Say that the order of traversal does not matter here, then pick one.
• Mention that the iterative version avoids deep recursion on skewed trees.
• A natural follow-up is Symmetric Tree (LeetCode 101), which compares a tree to its own mirror without changing it.

For live help while you talk through tree problems, see Linkjob AI, an interview assistant I work on (disclosure: I am part of the Linkjob AI team).