Invert Binary Tree

EasyTree DFSBlind 75JuniorOpen on LeetCodeUpdated Sep 21, 2026

You're given the root of a binary tree. Invert it by swapping the left and right child of every node, so the result is the mirror image of the original tree. Return the root of the inverted tree. You may rearrange the existing nodes rather than building new ones. An empty tree stays empty, so return null for it.

Examples

root = [4,2,7,1,3,6,9] returns [4,7,2,9,6,3,1]

input

output

Every node's two children have swapped sides.

The root 4 stays put while its children 2 and 7 trade sides. The same swap happens one level down, so 7 (now on the left) holds 9 then 6, and 2 (now on the right) holds 3 then 1.

root = [2,1,3] returns [2,3,1]

Swapping the two children of 2 puts 3 on the left and 1 on the right.

root = [] returns []

An empty tree has nothing to swap, so the answer is also empty.

Constraints

0 <= number of nodes <= 100
-100 <= Node.val <= 100

Hints

Hint 1

Look at what mirroring does to one node and its two children, then ask what must already be true of each subtree.

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Recursive depth-first search (DFS). Invert the left and right subtrees, then swap the current node's two child pointers and return the node. Every node has its children swapped exactly once, and a tree whose every node is swapped is the mirror image of the original. O(n) time, O(h) space for the recursion stack, where h is the tree height (O(n) for a skewed tree).

Time

O(n)

Space

O(h)

Pitfall

Writing root.left = invert(root.right) and then root.right = invert(root.left) reads root.left after you already overwrote it, so both sides end up the same subtree. Save both results before reassigning.

Solutions

class Solution {
    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;
    }
}

from typing import Optional

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root