4
root
Mirror a binary tree left-to-right. The whole problem reduces to one move applied everywhere: swap each node's two children, then recurse. A textbook tree-DFS in linear time.
Given the root of a binary tree, return its mirror image: every node's left and right subtrees are flipped. For [4,2,7,1,3,6,9] the answer is [4,7,2,9,6,3,1] — node 4 keeps its place, but its children 2 and 7 swap, and that same flip cascades all the way down (1/3 → 3/1, 6/9 → 9/6).
swap(node.left, node.right). Do it at the root and recurse, and the entire tree mirrors itself. The recursion is the algorithm.null, return null — an empty subtree is already its own mirror.left and right pointers. This is the only mutation.You must touch every node once, so time is O(n) either way. Recursive DFS uses O(h) call-stack space (O(log n) balanced, O(n) degenerate). An iterative BFS with a queue (or DFS with an explicit stack) is identical in spirit — pop a node, swap its children, enqueue them — and avoids deep recursion.
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 null; // empty subtree: nothing to flip
// swap the two child pointers...
const tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left); // ...then recurse into both sides
invertTree(root.right);
return root; // same node object, mirrored
}null subtree is already a mirror of itself, so return null. This also terminates the recursion at the leaves' children.root.left and root.right via a temp (or a destructuring swap). Because these are pointers, the entire subtrees move with them — you never touch grandchildren directly.invertTree on the new left and the new right. Each subtree mirrors itself independently; the order of the two calls is irrelevant.| "mirror / flip / invert a tree" | swap children + DFS |
| same op at every node | recurse(root): do-thing; recurse(L); recurse(R) |
| deep / skewed tree, avoid stack overflow | iterative BFS queue or DFS stack |
| "is it symmetric?" next | compare tree to its mirror (two pointers) |
function invertTree(root: TreeNode | null): TreeNode | null {
if (!root) return null;
[root.left, root.right] = [root.right, root.left]; // swap
invertTree(root.left);
invertTree(root.right);
return root;
}