Skip to content
DSA Grind
All 26 sections

Invert Binary Tree (LC 226)

ProblemEasyLeetCode 226Updated
On this page

Pattern: DFS (Post-Order / Divide & Conquer on Tree)
Difficulty: Easy
Key Concept: Mirror the tree by swapping each node’s left and right children, then apply the same rule to every subtree.

Problem Statement

You are given the root of a binary tree. Invert the tree (mirror it left–right) and return the new root.

For every node, its left child should become what the right child was, and vice versa. Apply this at all nodes.

Input: TreeNode root — the root of a binary tree (may be null).
Output: TreeNode — the root of the inverted tree (same root reference, mutated structure).

Example (LeetCode-style array): [4,2,7,1,3,6,9] represents:

        4
      /   \
     2     7
    / \   / \
   1   3 6   9

After inversion, the tree matches [4,7,2,9,6,3,1].

1. Algorithm & Pseudocode

Brute force (BFS, level by level)

invertBFS(root):
  if root is null: return null
  queue = new queue containing root
  while queue is not empty:
    node = dequeue()
    swap node.left and node.right using a temporary variable
    if node.left is not null: enqueue(node.left)
    if node.right is not null: enqueue(node.right)
  return root

Idea: Visit nodes in breadth-first order; at each node, swap children. Every node is touched once; swaps propagate the mirror shape.

Optimal (DFS recursive)

invertDFS(node):
  if node is null: return null
  temp = node.left
  node.left = node.right
  node.right = temp
  invertDFS(node.left)
  invertDFS(node.right)
  return node

Idea: Swap before recursing so each subtree is already mirrored locally; recursion fixes the whole tree. Very short and clear.

Optimal (DFS iterative, explicit stack)

invertStack(root):
  if root is null: return null
  stack.push(root)
  while stack is not empty:
    node = stack.pop()
    swap node.left and node.right
    if node.left is not null: stack.push(node.left)
    if node.right is not null: stack.push(node.right)
  return root

Idea: Same as recursive DFS, but you manage the stack yourself (use Deque in Java).

2. Step-by-Step Analysis (Beginner-Friendly)

  1. Why swap at every node?
    Inverting is “mirror.” For a single node, mirroring means its left and right subtrees trade sides. If you do that for every node, the entire tree flips.

  2. Why does BFS still work?
    Order does not matter for correctness as long as each node is visited once and you swap its two child pointers. BFS just uses a queue instead of the call stack.

  3. Why is DFS often called “optimal” here?
    All correct single-pass solutions are O(n) time and O(h) or O(n) extra space (recursion stack vs queue). “Optimal” usually means the tiny recursive solution: minimal code, same asymptotic bounds, easy to reason about.

  4. Why a temporary variable in Java?
    You cannot swap two references in one expression without losing one side. TreeNode temp = node.left; node.left = node.right; node.right = temp; saves the old left before overwriting.

  5. What about null?
    If root is null, there is nothing to invert; return null immediately.

3. The Dry Run

Sample tree (LeetCode array [4,2,7,1,3,6,9]):

        4
      /   \
     2     7
    / \   / \
   1   3 6   9

Recursive DFS (swap first, then recurse).
We trace invertTree(node) calls. After each swap at a node, we show left / right of that node.

Step Action node node.left node.right Notes
1 Enter invert(4) 4 2 7 Before swap
2 Swap at 4 4 7 2 Children exchanged
3 Recurse invert(7) 7 6 9 Before swap at 7
4 Swap at 7 7 9 6
5 invert(9) 9 null null No swap needed; return
6 invert(6) 6 null null Return
7 Return from invert(7) — — — Subtree rooted at 7 is mirrored
8 Recurse invert(2) 2 1 3 Before swap
9 Swap at 2 2 3 1
10 invert(3) 3 null null Return
11 invert(1) 1 null null Return
12 Return from invert(2) — — — Subtree rooted at 2 is mirrored
13 Return invert(4) 4 7 2 Whole tree inverted

Final tree:

        4
      /   \
     7     2
    / \   / \
   9   6 3   1

4. Java Solution

Brute Force

Approach: BFS with a queue; at each node, swap left and right, then enqueue non-null children.

Time: O(n) — each node visited once.
Space: O(w) for the queue, where w is max width; worst case O(n).

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }
}

Optimal

Approach 1 — Recursive (elegant): Swap children, recurse on both subtrees.

Time: O(n). Space: O(h) call stack (h = height; O(n) skewed tree).

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

Approach 2 — Iterative DFS (stack):

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        return root;
    }
}

5. The “Java vs. Others” Edge

  • Swapping with a temp: In Java, TreeNode references are swapped with TreeNode temp = node.left; node.left = node.right; node.right = temp;. C++ with raw pointers looks similar; Python can swap with tuple unpacking: node.left, node.right = node.right, node.left.
  • Queue / stack: Prefer ArrayDeque over legacy Stack for iterative DFS; it is not synchronized and performs better.
  • Famous story: This problem is often cited in connection with the “Homebrew incident” — Max Howell tweeted that Google rejected him after he could not invert a binary tree on the whiteboard. The lesson for interviews: a small tree problem can still trip you up under pressure; knowing swap + recurse cold is valuable.

6. Complexity Summary

Approach Time Space Notes
Brute Force (BFS) O(n) O(w) ≤ O(n) Queue holds up to one level; worst width n
Optimal (DFS recursive) O(n) O(h) Recursion depth = tree height
Optimal (DFS stack) O(n) O(h) Explicit stack replaces call frames

Here n = number of nodes, h = height, w = max breadth.