Invert Binary Tree

Given the root of a binary tree, invert it (mirror it left-to-right) and return the root.

Examples

Input:        4                 Output:       4
            /   \                            /   \
           2     7      ==>                 7     2
          / \   / \                        / \   / \
         1   3 6   9                       9   6 3   1

Constraints

• 0 <= number of nodes <= 100.

Approach — swap children at every node

Inverting a tree means: at every node, swap its left and right subtrees. If you do that swap recursively all the way down, the whole tree ends up mirrored. This is a textbook depth-first recursion.

Solution

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

Iterative version with an explicit queue (avoids deep recursion):

from collections import deque

def invert_tree(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node:
            node.left, node.right = node.right, node.left
            queue.append(node.left)
            queue.append(node.right)
    return root

Explanation

• Base case: an empty subtree (None) inverts to itself — this stops the recursion.
• Recursive case: invert both subtrees, then swap them. The tuple assignment evaluates the right side fully before assigning, so recursing on the original root.right and root.left is safe — no need for a temp variable.
• The iterative version does the same swap but uses a queue instead of the call stack.

Complexity

• Time: O(n) — every node is visited once.
• Space: O(h) for recursion (h = tree height; O(n) worst case for a skewed tree), or O(n) for the queue.

Interview tips

Famous for the "Homebrew author rejected by Google over this" tweet. It's genuinely easy — the interviewer is checking clean recursion and the empty-tree base case, not trickery.