Invert Binary Tree

EasyBinary Tree · Post-Order DFS🧩 Tree DFS LeetCode #226 ↗Updated Oct 30, 2026

Problem

You get the root of a binary tree. Turn it into its mirror image — at every node the left and right subtrees trade places — and return the root of the mirrored tree. An empty tree stays empty.

Input[4,2,7,1,3,6,9]Output[4,7,2,9,6,3,1]

Input[2,1,3]Output[2,3,1]

Input[]Output[]

0 ≤ n ≤ 100 · -100 ≤ Node.val ≤ 100

Try it yourself

Java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Mirroring a tree = swap the two children of every node. The order in which nodes are visited does not matter, so any traversal (recursive, BFS, stack) works.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceBuild a Mirrored Copy

Time O(n)Space O(n)

Create a brand-new tree: the copy of a node gets the mirrored right subtree as its left child and the mirrored left subtree as its right child. The input is left untouched.

Java

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    return new TreeNode(root.val, invertTree(root.right), invertTree(root.left));
}

Correct and side-effect free, but allocates n new nodes for no reason.

BetterBFS Queue, Swap In-Place

Time O(n)Space O(w)

Walk the tree level by level with a queue; for each polled node swap its left/right pointers, then enqueue the non-null children. No new nodes, no recursion. w = max level width (up to n/2).

Java

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        TreeNode tmp = cur.left; // swap children
        cur.left = cur.right;
        cur.right = tmp;
        if (cur.left != null) queue.offer(cur.left);
        if (cur.right != null) queue.offer(cur.right);
    }
    return root;
}

In-place and stack-overflow proof, but the queue can hold a whole level.

OptimalRecursive Post-Order Swap

Time O(n)Space O(h)

Invert both subtrees first, then hang them back on the opposite sides. Each node is touched once; the only extra memory is the call stack, which is O(h) — O(log n) when balanced, O(n) when skewed.

Java

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

Three lines, in-place, mirrors the recursive definition of a tree.

Pro tip

Inverting twice gives back the original tree — a handy self-check when testing.

At a glance

Level	Approach	Time	Space
Brute Force	Build a Mirrored Copy	`O(n)`	`O(n)`
Better	BFS Queue, Swap In-Place	`O(n)`	`O(w)`
Optimal	Recursive Post-Order Swap	`O(n)`	`O(h)`

Common pitfalls

Assigning root.left = invertTree(root.right) first, then reusing the overwritten root.left.
Swapping only values of leaves, or only the root's children — every level must be mirrored.
Forgetting the null base case / empty-tree input.

Interview tips

Say it in one line: “swap children at every node” — then pick a traversal.
Mention the recursion depth risk on a skewed tree and offer the BFS/stack version.
Clarify whether mutating the input is allowed; if not, return a mirrored copy.

Pattern

Tree DFS (post-order) → transform every node using results already computed for its subtrees.

My notes saved in this browser