Invert Binary Tree

Approach Summary

Recursively swap left and right children at every node. Post-order or pre-order both work.

Full Solution & Approach

Mirroring a binary tree is textbook recursion: swap the left and right children, then recurse on both. Base case: a null node has nothing to invert, so return null. For a non-null node, swap root.left and root.right, then call invertTree on each — the swap can happen before or after the recursion because the subtrees are treated independently. Because every node is visited exactly once and each visit does O(1) work (a swap), the time is O(n). Space is the recursion depth — O(h) where h is the tree height, worst case O(n) for a skewed tree. The iterative version with a stack performs the same swaps in any order. This warm-up tests your comfort with the tree-recursion pattern before harder DFS problems.

Every node is visited once with constant work — O(n) time. Recursion depth equals the tree height — O(h) space, O(n) worst case for a skewed tree.

Solution Code

Solution

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

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

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

Edge Cases to Watch

Empty tree — returns null
Single node — children swapped (both null), returns the node
Skewed tree — recursion depth equals height; use an iterative stack on very deep trees to avoid stack overflow

How to Recognize This Pattern

Mirror a tree
Swap children at every node

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)