Invert Binary Tree

Examples

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

At every node, the left and right subtrees swap. The 2-subtree and 7-subtree swap places under the root, and the same swap happens one level down.

Input: root = [2,1,3]
Output: [2,3,1]

The root's two children, 1 and 3, swap sides.

Input: root = []
Output: []

An empty tree, mirrored, is still empty.

Constraints

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

Approach

A tree is mirrored when every single node - not just the root - has its left and right children swapped. That "do the same thing at every level" phrasing is a strong hint to solve it recursively: invert the left subtree, invert the right subtree, and then swap the two (now-inverted) subtrees onto the current node.

The same idea also works iteratively with an explicit stack or queue: visit each node once, swap its children, and push those children on to be visited later. Both approaches touch every node exactly once.

Solutions

Recursive DFS

Invert the left subtree and the right subtree first, then swap them onto the current node. The base case is an empty node, which is already its own mirror image.

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

function invertTree(root) {
  if (root === null) return null;

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

  root.left = right;
  root.right = left;

  return root;
}

Time: O(n) · Space: O(h) — recursion stack depth, where h is the tree's height (O(n) worst case for a skewed tree)

Iterative BFS

Use a queue to visit every node level by level. At each node, swap its children, then push both children onto the queue so they get swapped too.

function invertTree(root) {
  if (root === null) return null;

  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();

    [node.left, node.right] = [node.right, node.left];

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return root;
}

Time: O(n) · Space: O(n) — the queue can hold up to a whole level of nodes