Invert Binary Tree

Invert a binary tree by swapping the left and right children of every node.

Why this is worth learning

Inversion is a structural permutation of existing child pointers, not a sort of values. The root node itself remains the same object.

Before coding: one-minute experiment

After inverting a root with only a left child, where is that same child node?

Function signature

func InvertTree(root *TreeNode) *TreeNode

Inputs / outputs

• root: root of the tree (may be nil).
• Return: root of the inverted tree.

Example

    4           4
   / \         / \
  2   7  ->   7   2
 / \ / \     / \ / \
1  3 6  9   9  6 3  1

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

The output must preserve node objects while reflecting their positions. At a node, the original right subtree belongs on the left after it too is reflected; the original left belongs on the right. Thus each child can solve the same task independently and the parent swaps their results. Saving both child results before assignments avoids losing an original reference. Swapping before recursion and swapping after recursion are both valid schedules if each original subtree is processed exactly once; neither requires allocating replacement nodes.

Invariant: after processing a node, its left and right subtrees are inverted.

Algorithm (step-by-step)

1. If root is nil, return nil.
2. Swap root.Left and root.Right.
3. Recurse on both children.
4. Return root.

Correctness sketch

An empty subtree remains empty. For a real node, exchange its left and right subtree roots, then invert each resulting subtree. By the inductive hypothesis, each child subtree is transformed into its mirror. Exchanging their positions and mirroring their interiors creates exactly the mirror of the entire original subtree. Every original node remains present once, with its value unchanged, and no new tree nodes are needed. Returning the original root pointer gives the caller access to the mutated tree.

Trace (hand walkthrough)

Example input:
    4           4
   / \         / \
  2   7  ->   7   2
 / \ / \     / \ / \
1  3 6  9   9  6 3  1

Walk:
- swap children of 4 -> left=7, right=2
- swap children of 2 -> left=3, right=1
- swap children of 7 -> left=9, right=6

Pitfalls to avoid

• Forgetting to handle nil nodes.
• Overwriting one child before saving it. The reference inverts both original children into local variables before assigning the swapped pointers; swapping first and then recursing also works.

Debugging lens

Record every original node's left and right pointers, then verify they are exchanged after inversion. Double inversion is an additional check, not a substitute for checking one correct inversion.

Complexity

• Time: O(n).
• Extra space: O(h) recursion depth.

Implementation notes (Go)

• An iterative BFS/DFS with a stack or queue works as well.

Contract precision

The tree is mutated in place; all original node identities and values are preserved. The returned pointer is the original root, including nil.

Reconstruction checkpoint

A root has left subtree L and right subtree R. Is it valid to invert L and R recursively before swapping them? What property should two consecutive inversions satisfy, including node identities?

Return to Binary Tree General · Module quiz