Invert Binary Tree

EasyTreesTreeDFSBFSBinary Tree

Problem

You are given the root of a binary tree and must produce its mirror image: at every node, the left and right subtrees trade places, all the way down to the leaves.

Example. A root of 4 with left child 2 (children 1 and 3) and right child 7 (children 6 and 9) becomes a root of 4 with left child 7 (children 9 and 6) and right child 2 (children 3 and 1).

Key idea

Copying the tree into an array and rebuilding it in reverse order adds bookkeeping the problem does not need. Inverting a tree is really just inverting its left subtree, inverting its right subtree, and exchanging the two results.

That recursive definition is the traversal itself. At each node, recurse into the left and right children to invert them, then swap the node's left and right pointers (the order of swap versus recursion does not matter, since the subtrees are independent). Every node is visited once, with constant work per node. The same idea also runs iteratively: push the root onto a queue, and each time you pop a node, swap its two children and push whichever are non-null. That avoids recursion depth entirely, which matters on very unbalanced trees.

Solution

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

  // recurse first, then swap; order does not matter since the subtrees are independent
  const invertedLeft = invertTree(root.left);
  const invertedRight = invertTree(root.right);

  // swap the child pointers, not the values, to mirror the shape
  root.left = invertedRight;
  root.right = invertedLeft;

  return root;
}

Complexity

  • Time: O(n). Every node is visited once and swapped in constant time.
  • Space: O(h). Recursion stack depth equals the tree's height, or O(n) worst case with an explicit queue holding a full level.

Watch out for

  • Null nodes must simply return immediately; do not treat them as an error case.
  • Swap the child pointers, not the node values: inverting values would leave the shape unchanged.
  • A linked-list-shaped tree makes recursive depth equal to n; the iterative queue version avoids that risk.

Pattern

This is the simplest structural tree transformation: define the operation on a whole tree in terms of the same operation on its subtrees, then let the traversal do the rest. The same divide-and-conquer shape, solving children first and combining at the parent, recurs throughout tree problems, from computing depth to checking balance.

Related questions