46.Invert Binary Tree

EasyBlind 75Trees · 1/15

Problem

Given the root of a binary tree, invert the tree and return its root. Inverting means mirroring the tree left-to-right: at every node, the left child and the right child swap places.

The values themselves never move between nodes — only the left / right pointers change.

Examples

Input:  root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation: Every level is read in reverse order after mirroring.

Input:  root = [2,1,3]
Output: [2,3,1]

Input:  root = []
Output: []
Explanation: An empty tree is its own mirror.

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

💡 Key Insight

The mirror of a tree is obtained by swapping the children of every node — the order in which nodes are visited does not matter, as long as each node is visited exactly once. So any traversal works: a queue (BFS), an explicit stack (DFS), or plain recursion. Each runs in O(n); they only differ in what the auxiliary space depends on (width vs. height).

BFS with a Queue

TimeO(n)SpaceO(w)

Intuition

Visit the tree level by level. Whenever a node is dequeued, swap its two children, then enqueue those children so they get swapped too. Since every node is processed once, the whole tree ends up mirrored.

Algorithm

If root is null, return null.
Push root into a queue.
While the queue is not empty:
- Poll a node, swap node.left and node.right.
- Enqueue each non-null child.
Return root.

Visualization

Queue processing on [4,2,7,1,3,6,9]

poll 4 -> swap (2,7) -> children now (7,2)   queue: [7, 2]
poll 7 -> swap (6,9) -> children now (9,6)   queue: [2, 9, 6]
poll 2 -> swap (1,3) -> children now (3,1)   queue: [9, 6, 3, 1]
poll 9, 6, 3, 1 -> leaves, swapping null/null changes nothing

Code

java

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // mirror this node
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

Complexity

Time: O(n) — every node is enqueued and swapped exactly once.
Space: O(w) — the queue holds at most one level; for a complete tree the last level has about n/2 nodes, so O(n) worst case.

Iterative DFS with a Stack

TimeO(n)SpaceO(h)

Intuition

Same idea, but use a stack instead of a queue. The visiting order becomes depth-first, which does not affect the result because each swap is independent of the others. The stack only ever holds pending siblings along one root-to-leaf path, so space tracks the height rather than the width.

Algorithm

If root is null, return null.
Push root onto a stack.
While the stack is not empty:
- Pop a node, swap its children.
- Push each non-null child.
Return root.

Visualization

stack: [4]
pop 4 -> swap -> 4(7,2)   push 7, 2   stack: [7, 2]
pop 2 -> swap -> 2(3,1)   push 3, 1   stack: [7, 3, 1]
pop 1, pop 3 (leaves)                 stack: [7]
pop 7 -> swap -> 7(9,6)   push 9, 6   stack: [9, 6]
pop 6, pop 9 (leaves)                 stack: []

Code

java

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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 tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return root;
    }
}

Complexity

Time: O(n) — each node is pushed and popped once.
Space: O(h) — the stack holds O(1) pending siblings per level of the current path; O(n) for a skewed tree.

Recursive DFSOptimal

TimeO(n)SpaceO(h)

Intuition

The definition is naturally recursive: the mirror of a tree rooted at node is node with its left subtree set to the mirror of the old right subtree and its right subtree set to the mirror of the old left subtree. The base case is an empty tree, whose mirror is itself. This is the same O(n) work as the iterative versions, but the shortest and clearest to write.

Algorithm

If root is null, return null.
Recursively invert root.left and root.right, saving the results.
Assign root.left = invertedRight and root.right = invertedLeft.
Return root.

Dry Run

flowchart TD
    subgraph Before
        A4["4"] --> A2["2"]
        A4 --> A7["7"]
        A2 --> A1["1"]
        A2 --> A3["3"]
        A7 --> A6["6"]
        A7 --> A9["9"]
    end
    subgraph After
        B4["4"] --> B7["7"]
        B4 --> B2["2"]
        B7 --> B9["9"]
        B7 --> B6["6"]
        B2 --> B3["3"]
        B2 --> B1["1"]
    end

The recursion first finishes subtree 2 (becoming 2 -> 3, 1), then subtree 7 (becoming 7 -> 9, 6), and finally swaps them under 4.

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // invert both subtrees first, then cross-assign them
        TreeNode invertedLeft = invertTree(root.left);
        TreeNode invertedRight = invertTree(root.right);
        root.left = invertedRight;
        root.right = invertedLeft;
        return root;
    }
}

Complexity

Time: O(n) — each node is visited once and does O(1) work.
Space: O(h) — recursion depth equals the tree height: O(log n) when balanced, O(n) when skewed.

Complexity Comparison

Approach	Time	Space
BFS with a Queue	O(n)	O(w) — up to O(n)
Iterative DFS with a Stack	O(n)	O(h)
Recursive DFS	O(n)	O(h)

Common Pitfalls

Writing root.left = invertTree(root.right); root.right = invertTree(root.left); — the second line reads the already overwritten root.left. Save the results in temporaries first.
Forgetting the null root case — calling methods on null throws a NullPointerException.
Swapping only the root's children (or only one level); every node in the tree must be swapped.
Creating new nodes instead of re-pointing existing ones is allowed but wastes O(n) memory for no benefit.