Invert Binary Tree

This is the classic first tree question, and it is short on purpose. The interviewer wants to see the core-idea habits under light pressure: a clean base case, trust in the recursive call, and an answer to "what if the tree is very deep?" Candidates who rush it often forget to return the root, or lose a subtree by swapping in the wrong order.

It is also a good place to practise the difference between building a new structure and changing the existing one — a distinction that matters in every tree problem that returns a tree.

The problem

Given the root of a binary tree, turn it into its mirror image — every left child becomes a right child and vice versa, at every level — and return the root.

before:        6                after:         6             /   \                           /   \            2     9                         9     2           / \   /                           \   / \          1   4 8                             8 4   1

• Input: the tree on the left (level order [6, 2, 9, 1, 4, 8]) → output: the tree on the right (level order [6, 9, 2, null, 8, 4, 1]).
• Input: an empty tree → output: an empty tree.

Constraints: 0 ≤ n ≤ 10⁵ nodes, and the tree is not guaranteed to be balanced.

Clarifying questions

• In place, or a new tree? In place is the usual expectation; ask. It decides whether you allocate new nodes.
• Return what? The root of the mirrored tree — the same root object as the input.
• Can the tree be empty? Yes; return None.
• How deep can it get? Up to 10⁵ with no balance promise. That rules out plain recursion in Python — see Approach 3.

Approach 1: the simple way — build a mirrored copy

The most direct reading of "mirror image" is to build a new tree where each new node's left subtree is the mirror of the old right subtree, and vice versa.

1def mirror_copy(root: Optional[TreeNode]) -> Optional[TreeNode]:2    """Build a new tree that is the mirror image of root."""3    if root is None:4        return None5    return TreeNode(root.val, mirror_copy(root.right), mirror_copy(root.left))

Time is O(n): one new node per old node. Space is O(n) for the copy, plus O(h) for the recursion.

This one is not too slow — trees rarely have a slow brute force. It falls short in two other ways. It allocates n new nodes when the problem asks you to change the tree in place, and any other code holding references to the old nodes will not see the change. And it recurses to depth h, which crashes in Python when h passes about 1,000.

The key insight

Mirroring a tree is the same as swapping the two children of every node. Nothing else changes: values stay in their nodes, and each node keeps the same parent.

Why is that enough? Apply the core idea's one-sentence test. "After invert(node) returns, the subtree at node is mirrored." At a node, swap its two children, then mirror each child's subtree. The left side now holds the mirrored old right side, and the right side holds the mirrored old left side — exactly the mirror of the whole subtree.

And the order does not matter. Each swap touches only one node's two links, so the swaps are independent. You can swap before recursing (preorder), after (postorder), or visit nodes level by level with a queue. All give the same result. That freedom is what lets us drop recursion entirely.

Approach 2: swap recursively, in place

1def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:2    """Mirror the tree in place and return its root."""3    if root is None:4        return None5    root.left, root.right = root.right, root.left   # swap this node's children6    invert_tree(root.left)7    invert_tree(root.right)8    return root

Python's tuple assignment evaluates the right side fully before assigning, so root.left, root.right = root.right, root.left swaps without a temporary variable. In Java or C++ you need the temporary, and writing root.left = root.right first loses the old left subtree forever.

Time is O(n) — one swap per node. Extra space is O(h) for the call stack: O(log n) when balanced, O(n) for a chain.

Approach 3: swap with a queue

Because the order of swaps does not matter, a queue can hand out the nodes instead of the call stack.

1from collections import deque234def invert_tree_iterative(root: Optional[TreeNode]) -> Optional[TreeNode]:5    """Mirror the tree in place without recursion."""6    queue = deque([root]) if root else deque()7    while queue:8        node = queue.popleft()9        node.left, node.right = node.right, node.left10        if node.left:11            queue.append(node.left)12        if node.right:13            queue.append(node.right)14    return root

Dry run on the example tree

After step 1 the root's children are 9 and 2, so 9 is processed next — it is now on the left. Reading the finished tree level by level gives [6, 9, 2, null, 8, 4, 1], the expected output.

Complexity. Time is O(n): each node is pushed and popped once. Extra space is O(w), the widest level — and no recursion, so a chain of 10⁵ nodes is handled without a RecursionError. A stack instead of a queue works just as well and uses O(h).

Edge cases

• Empty tree. All three versions return None without touching anything.
• A single node. Its two None children swap with each other; the tree is unchanged.
• A chain. A left-only chain becomes a right-only chain. The recursive version needs one frame per node; the queue version holds one node at a time.
• Inverting twice. Mirroring the mirror gives back the original tree — a free self-test. Run your function twice and compare.

Saying it in the interview

Follow-ups

• "Check whether a tree is symmetric." Do not invert and compare (that changes the input). Walk two pointers from the root's children inward: left.left against right.right, and left.right against right.left.
• "Check whether one tree is the mirror of another." Same two-pointer recursion, with one pointer in each tree.
• "Keep the original unchanged." Use Approach 1, the mirrored copy — now its extra O(n) memory is the point, not a flaw.