Invert Binary Tree

Invert a binary tree by swapping the left and right children of every 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)

Recursively swap children at every node.

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

• Invariant: after processing a node, its left and right subtrees are inverted.
• Base cases handle nil/leaf nodes correctly.
• Recursive calls return correct results for subtrees (induction).
• Combining subtree results yields the correct answer for the current node.

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.
• Swapping after recursion (works too, but be consistent).

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.