Overview

Given the root of a binary tree, invert it — swap the left and right children of every node — and return the root.

Implement invertTree(root).

This was famously the subject of a tweet by Max Howell about the Google interview process.

Constraints

• Tree nodes have shape { val, left, right }.
• The tree may be null (return null).
• The inversion must be applied recursively to all nodes, not just the root.
• Modify the tree in place and return the root.

Examples

//     4              4
//    / \\           / \\
//   2   7   →     7   2
//  / \\ / \\      / \\ / \\
// 1  3 6  9    9  6 3  1
invertTree(root);  // returns the modified root

//   2        2
//  /    →     \\
// 1            1
invertTree(root);  // returns modified root

Notes

• Recursive approach: swap left and right children, then recursively invert each subtree.
• Base case: if the node is null, return null.
• Can also be done iteratively with a queue (BFS) — process each node, swap its children, and enqueue them.
• $O(n)$ time, $O(H)$ space for recursion stack.

Solution

function invertTree(root) {
  if (!root) return null;
  const temp = root.left;
  root.left = root.right;
  root.right = temp;
  invertTree(root.left);
  invertTree(root.right);
  return root;
}

Resources

• Invert Binary Tree — LeetCode
• Binary Tree — Wikipedia