Invert Binary Tree

Difficulty: Easy

Problem

Given the root of a binary tree, produce its mirror image and return the new root. Mirroring means that at EVERY node, the left child and the right child trade places.

Example

Input: root = [1,2,3,4,5,null,6]
Output: [1,3,2,6,null,5,4]
Explanation: At the root, children 2 and 3 swap. Under 2, nodes 4 and 5 swap; under 3, the missing left child and 6 swap, so 6 becomes the left child. The whole tree becomes its mirror image.

Brute-force approach

There is no meaningful 'brute force vs optimal' split here. The recursive swap IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: One tiny action (swap my two children) applied at EVERY node produces the full mirror image. Recursion is the machine that applies it everywhere.

Recursively swap the left and right children of every node. Do the swap at the current node, then let recursion handle both subtrees.

Steps

  1. Base case: if the node is null, return null
  2. Swap the node's left and right child pointers
  3. Recursively invert the (new) left subtree
  4. Recursively invert the (new) right subtree
  5. Return the node

Time complexity: O(n) · Space complexity: O(h) where h = height of tree

Pseudocode

function invertTree(root):
    if root is ____:
        return null
    
    swap(root.____, root.____)
    
    invertTree(root.left)
    invertTree(root.____)
    
    return ____

Hints

  • Base case: what kind of node needs no inverting at all? (An empty one!)
  • The swap: which two pointers of the current node trade places?
  • After swapping, recurse into BOTH children. Each subtree still needs mirroring inside
  • The problem wants the tree back: what do we return at the end?

Complexity questions

What is the time complexity of inverting a binary tree with n nodes?

O(n). Every node is visited exactly once, and each visit does O(1) work (one pointer swap). Total: O(n).

What is the space complexity of the recursive solution?

O(h): the recursion call stack, where h is the tree height. We don't allocate new nodes (the swap is in-place), but recursion isn't free: the call stack grows as deep as the tree. That's O(h): O(log n) for a balanced tree, O(n) for a completely skewed one.

Node X has 1,000 nodes in its left subtree. How expensive is swapping X's left and right pointers?

O(1): only two pointers change. This is the beautiful part: we never touch the 1,000 nodes. Swapping two pointers is a constant-time operation no matter how big the subtrees are: the subtrees 'move' because their handle moved.

Could we invert the tree WITHOUT recursion?

Yes: use a queue (BFS) or an explicit stack, swapping children at each visited node. Any tree traversal works: visit every node once, swap its children when you visit it. BFS with a queue or DFS with an explicit stack both give O(n) time. Recursion is just the most elegant way to write it.

Check your understanding of Invert Binary Tree

What does 'inverting' a binary tree actually mean?

Swap the left and right children of every node. Inverting = mirroring. Every node keeps its value, but its left and right subtrees trade places. No values change and no nodes move up or down a level, only left/right flips.

If we invert the tree [2,1,3] (root 2, left 1, right 3), what do we get?

[2,3,1]. The root stays 2. Its children 1 (left) and 3 (right) swap places, giving root 2, left 3, right 1 → [2,3,1].

Do we swap the node VALUES or the node POINTERS (left/right references)?

Pointers: entire subtrees move with one swap. We swap the pointers: root.left and root.right trade places. This is powerful. When a pointer moves, the ENTIRE subtree hanging from it moves too, in a single O(1) operation.

What is the base case for the recursive invert?

When the node is null (empty). Null is the base case: an empty subtree needs no inverting, so we just return. Note a LEAF is not the base case: we still 'swap' its two null children (harmlessly) and recurse into them.

After swapping a node's children, why do we still need to recurse into the subtrees?

Because the swap only mirrors ONE level; the subtrees inside are still un-mirrored. Swapping at node X only fixes X's immediate children. The subtrees that moved still have their ORIGINAL left/right arrangement inside. Every node needs its own swap, recursion delivers exactly that.

Related problems

Keep practising