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. (The animation and walkthroughs use the fuller tree [4,2,7,1,3,6,9]; this statement example is chosen because node 3 has only one child.)

Brute-force approach

The first idea is to manufacture a second, mirrored tree: allocate a fresh node for every old node and hang the old right subtree's copy on the new left, and the old left subtree's copy on the new right. It is correct, but it allocates n new nodes (6 for [1,2,3,4,5,null,6], 7 for [4,2,7,1,3,6,9]) and holds two full trees at once (12 and 14 nodes in memory), while the original is left un-inverted.

Steps

  1. If the node is None, return None
  2. Create a brand-new node with the same value
  3. Set new.left to the mirrored copy of the old RIGHT subtree
  4. Set new.right to the mirrored copy of the old LEFT subtree
  5. Return the new node

Time complexity: O(n) · Space complexity: O(n) extra: n new nodes, two trees in memory

Trade-offs

  • n fresh node allocations for an answer that needs none
  • The original tree is still there un-inverted, so two full trees are held at once

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?
  • A leaf is not the base case, and neither is a node with one child: its swap carries the missing child across (in [1,2,3,4,5,null,6], node 3 has only 6, and after the swap 6 is its LEFT child).
  • Python tip: a chain of about 1,000 nodes is the most the recursive version can invert from the top of a script; for deeper trees use the iterative version (a queue or a stack).

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. (Python also stops the recursion near 1,000 nested calls, so a chain of about 1,000 nodes is the limit for the recursive version.)

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