Blind 75Easy

Invert Binary Tree — Recursive Swap

Swap left and right children at every node using recursion or BFS to mirror the tree.

TreeBFS

View problem on LeetCode

Problem Statement

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

Why This Problem Matters

Simple yet popular question verifying comfort with tree recursion.
Highlights symmetry operations on trees.
Serves as warm-up for more complex tree manipulations.

Thought Process

Swap children at each node

Recursively invert left and right subtrees after swapping to avoid extra storage.

Handle null nodes gracefully

Base case returns null when encountering empty subtrees.

Iterative alternative

BFS queue can invert level by level if recursion depth is a concern.

Step-by-Step Reasoning

If root is null return null.
Swap left and right pointers.
Recursively invert left, then right.
Return root.

Dry Run

Balanced tree root 4 with children 2 and 7

After inversion, left subtree becomes original right.

Single node

Nothing changes; recursion returns immediately.

Complexity Analysis

Time

O(n)

Space

O(h)

Why

Visit every node once; recursion depth equals tree height h.

Annotated Solution

JAVA

public class InvertBinaryTree {
  public TreeNode invertTree(TreeNode root) {
    if (root == null) {
      return null;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
  }

  public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
  }
}

Swapping before recursive calls ensures each subtree is inverted exactly once.

Common Pitfalls

Swapping after recursion inverts twice; swap before or store temporary.
Forgetting to return root leads to lost references.
Large skewed trees may overflow recursion stack—mention iterative BFS alternative.

Follow-Up Questions

How would you invert only nodes at even depth?
Can you verify the tree is symmetric without modifying it?

Key Takeaways

Tree recursion patterns are straightforward but must respect base cases.

Iterative BFS or DFS alternatives avoid stack-depth problems.

Inversion is equivalent to mirroring across the vertical axis.