Faangprep Logo
Log inStart free
Browse curriculum

Invert Binary Tree

Mirror a binary tree by swapping every node's left and right children with a depth-first traversal.

EasySolve on LeetCode

Problem Understanding

Invert Binary Tree: given the root of a binary tree, mirror it — every node's left and right children trade places — and return the root.

Example: [4, 2, 7, 1, 3, 6, 9] becomes [4, 7, 2, 9, 6, 3, 1].

Attempt 1: Rebuild the Tree Level by Level

One way is to read the tree level by level, reverse each level, and build a new tree from the result. It works, but it allocates a whole new tree and has to track where empty children belong. The mirror is a local change: each node only needs its own two child pointers swapped.

The Intuition: Swap, Then Let the Recursion Finish the Job

A tree is mirrored exactly when every node's children are swapped:

  1. If the node is null, there is nothing to do — return null.
  2. Swap the node's left and right pointers.
  3. Invert the (new) left subtree, then the (new) right subtree.
  4. Return the node.

Each node is swapped once, before its children, so the whole tree is mirrored in one depth-first pass. This is the DFS pattern in its simplest form: do the work at the node, then hand the same problem to each child.

Interactive Walkthrough

FILLED = CHILDREN ALREADY SWAPPED

CALL

Swapped

0 / 7

Stack depth

1

call stack

invertTree(4)

 

invertTree(4)

Next

Swap 4's children: left is now 7, right is now 2

Tree

The tree is redrawn from its links at every step, so each swap is visible as two subtrees trading sides. The calls in progress are outlined from the root down to the running one, swapped nodes fill in, and an empty child shows the null it returns.

The approach, step by step

  1. Stop at null

    If the node is null, return null.

  2. Swap the children

    Exchange the node's left and right child pointers.

  3. Recurse

    Invert the left subtree, then the right subtree, and return the node.

Frequently asked questions

How do you invert a binary tree?

Visit every node and swap its left and right children. Recursively: if the node is null return null; otherwise swap its children, invert the left subtree, invert the right subtree, and return the node.

Does it matter whether you swap before or after recursing?

No. Swapping first (pre-order) and swapping after both subtrees are inverted (post-order) both mirror the tree, because each node's children are swapped exactly once. Swapping between the two recursive calls (in-order) does not work: the second call would invert the subtree that was already inverted.

What is the time and space complexity of inverting a binary tree?

O(n) time, since each node is visited once. O(h) space for the recursion stack, where h is the tree's height: O(log n) for a balanced tree and O(n) for a skewed one. A breadth-first version with a queue also works in O(n) time.