#226 Invert Binary Tree

Problem Statement

Given the root of a binary tree, invert the tree, and return its root. Inverting means swapping the left and right subtrees at every node.

Intuition

Inverting a binary tree is a classic recursive problem. At each node, we swap the left and right children, then recursively invert each subtree.

Approach

1. If the node is null, return null (base case).
2. Swap the left and right children.
3. Recursively invert the left and right subtrees.
4. Return the node.

Solution

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;

  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

Complexity Analysis