Invert Binary Tree

Learning goal: Recognize that inverting a binary tree changes child pointers, not node values.

Core idea The inverted tree is the mirror image of the original around its root. A node keeps its own value, but its left child becomes its right child and its right child becomes its left child. This local operation must happen at every node, including nodes several levels below the root.

Algorithm plan

• If the current node is null, there is nothing to invert.
• Swap the current node's left and right pointers.
• Visit both child subtrees and perform the same operation.
• Return the original root after all pointers have been changed.

Micro-example For a node with left = 1 and right = 3, the node's value does not change. After inversion, left = 3 and right = 1.

Pitfalls

• Swapping values does not mirror the tree's structure.
• Swapping only the root leaves deeper nodes incorrect.
• A null root must return null safely.

Recap

• Inversion is a structural transformation.
• Every node swaps its two child references.
• The base case is a missing node.

Learning goal: Understand why one local swap, repeated through traversal, is sufficient.

Core idea The mirror relationship is defined independently at each node. Once a node swaps its children, the same rule can be applied to each child subtree without needing information from distant branches. This makes inversion a natural traversal problem: visit every node exactly once and perform one constant-time swap.

Data structure model

A binary tree node stores three important references:

The tree can be traversed recursively with the call stack, or iteratively with an explicit stack for DFS or a queue for BFS.

Micro-example At node 7, the original children are 6 and 9. After the local swap, 9 is on the left and 6 is on the right. The same rule later handles nodes 6 and 9.

Pitfalls

• Do not assume swapping at one level automatically fixes lower levels.
• Do not lose a child reference by overwriting before saving or swapping.
• The order of traversal affects visitation order, not the final result.

Recap

• Values remain attached to their nodes.
• Child references are exchanged at every node.
• DFS and BFS are both valid because all nodes must be touched.

Learning goal: Compare recursive DFS with iterative traversal and identify the stopping condition.

Core idea A recursive solution uses the function call stack as an implicit DFS stack. For each non-null node, swap its children and recursively invert both resulting subtrees. When the function receives null, it returns immediately because an empty subtree is already its own mirror.

Algorithm plan

1. Receive a node root.
2. If root is null, return null.
3. Exchange root.left and root.right.
4. Recursively process root.left.
5. Recursively process root.right.
6. Return root.

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

DFS, using recursion or an explicit stack, uses O(h) auxiliary space where h is the tree height. BFS uses a queue and can require O(w) space, where w is the maximum width. Both methods take O(n) time because each of the n nodes is processed once.

Micro-example At 4, swap 2 and 7. Then process the new left child 7 and new right child 2. The traversal order differs from the original child order, but every node is still visited.

Pitfalls

• Recurse into both subtrees after the swap.
• A recursion on only one child misses an entire branch.
• The base case must handle an empty tree and leaf children.

Recap

• Swap first, then traverse both children.
• null is the recursion stopping point.
• DFS and BFS produce the same final tree.

Learning goal: Trace one complete DFS inversion and connect each visit to the final level-order output.

Core idea We will use an explicit DFS stack to mirror the recursive process. At each node, the algorithm swaps the children and pushes the resulting children for later processing. The stack order is chosen so the new left subtree is processed first, matching recursive left-then-right DFS after the swap.

Algorithm plan

• Start with node 4 on the stack.
• Pop a node, mark it visited, and swap its children.
• Push the new right child first, then the new left child, so the left child is processed next.
• Continue until the stack is empty.

Micro-example At 4, the children change from (2, 7) to (7, 2). At 7, (6, 9) becomes (9, 6). At 2, (1, 3) becomes (3, 1).

Pitfalls

• After swapping, reason about the new left and right children.
• Do not process only the original left branch.
• A leaf still gets visited, but its two child references are both null.

Recap

• The transformed tree is [4,7,2,9,6,3,1] in level order.
• The DFS worklist is only an implementation detail.
• The essential action at every visit is one pointer swap.

Learning goal: Diagnose the two most common incorrect implementations and handle unusual tree shapes.

Core idea The algorithm is short, so most mistakes come from transforming the wrong part of the node or stopping too early. Swapping the values of two children may make one example look plausible, but it does not exchange the subtrees attached beneath those nodes. Likewise, swapping only one level or recursing into only one child leaves part of the tree unchanged.

Algorithm plan

• Check for null before accessing child pointers.
• Swap the references left and right, not the values stored in nodes.
• Continue into both children after the swap.
• Return the same root reference, now with mirrored descendants.

Micro-example If node 2 has subtree 1 on the left and subtree 3 on the right, exchanging values 1 and 3 does not move their descendants. Exchanging pointers moves the entire subtrees, which is the required operation.

Pitfalls

• Empty tree: return null.
• Single node: return it unchanged.
• A skewed tree still requires visiting every node.
• Deep recursion can be limited by stack depth in some languages.

Recap

• Swap pointers, never merely values.
• Recurse or iterate through both subtrees.
• Empty and leaf trees are naturally handled by the base case.

Learning goal: Justify the O(n) running time and O(h) recursive space bound.

Core idea Let n be the number of nodes and h the height of the tree. The algorithm performs a constant amount of pointer work at each node: one swap and the scheduling of two children. Since no node is revisited for additional computation, the total running time grows linearly with n.

Algorithm plan

• Count one visit for each non-null node.
• Charge the child swap to that node; it costs O(1).
• Add the recursion depth, which is at most the tree height h.
• Return the transformed root without allocating a second tree.

Micro-example The example contains 7 nodes, so DFS performs 7 swaps. Its recursion depth is 3 edges from the root to a leaf, giving auxiliary stack usage proportional to the height.

For a balanced tree, h is approximately log n; for a completely skewed tree, h can be n. The recursive solution therefore uses O(h) auxiliary space. An iterative BFS solution has O(w) queue space, where w is the maximum width, while iterative DFS also uses O(h) in the worst case.

Pitfalls

• Do not call the output space O(n) when modifying nodes in place.
• Time is still O(n) even if the tree is balanced.
• The height bound matters for recursion depth on skewed trees.

Recap

• Time: O(n) because every node is visited once.
• Recursive auxiliary space: O(h).
• In-place pointer swaps produce the mirror tree.