Invert Binary Tree

Why it belongs on this sheet

This is short, but it tells you whether binary-tree recursion already feels natural.

Pattern

Swap and recurse

Approach

For each node, swap its children and recursively invert both subtrees.

Java solution

class Solution {
  public TreeNode invertTree(TreeNode root) {
    if (root == null) {
      return null;
    }

    TreeNode temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);
    return root;
  }
}

Complexity

• Time: O(n)
• Space: O(h)

Interview note

It is often safer to store one child in a temporary variable before recursive calls.