EasyDepth-First SearchBreadth-First SearchTreeUpdated Sep 2026

226. Invert Binary Tree

Asked at Google, Meta, Amazon, Microsoft and 1 more

Difficulty

Easy

Time

O(n)

Space

O(h)

Pattern

Depth-First Search

Companies

5

Problem

You are given the root of a binary tree. Invert the tree and return its root.

Inverting means mirroring the tree: at every node, the left child and the right child trade places. Do this for the whole tree, not just the top node.

A node may have zero, one or two children. The tree can also be empty, in which case you return nothing (null).

Mirror the whole tree

1234679Input tree: 4 has children 2 and 79764321Output tree: 4 now has children 7 and 2, and eachsubtree is mirrored too
Every node swaps its two children, so the tree becomes its own mirror image.

Constraints

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

Examples

Example 1
Inputroot = [4,2,7,1,3,6,9]
Output[4,7,2,9,6,3,1]
WhyThe root 4 keeps its value, but its children 2 and 7 swap. Then inside the 2-subtree the children 1 and 3 swap, and inside the 7-subtree the children 6 and 9 swap. Reading the result level by level gives [4,7,2,9,6,3,1].
Example 2
Inputroot = [2,1,3]
Output[2,3,1]
WhyOnly the root has children here. Swapping 1 and 3 turns [2,1,3] into [2,3,1], and the two leaves have nothing left to swap.
Example 3
Inputroot = []
Output[]
WhyThere is no node at all, so there is nothing to swap and the result is also empty.

Asked At

5 companies
CompanyDifficulty
GoogleEasyView all Google questions →
MetaEasyView all Meta questions →
AmazonEasyView all Amazon questions →
MicrosoftEasyView all Microsoft questions →
AppleEasyView all Apple questions →

How to Think About It

1

Recursive approach: swap left and right children, then recurse on both subtrees. The base case is a null node.

2

Why it works: by swapping at every node, the entire tree becomes its mirror image. Left becomes right, right becomes left.

3

BFS alternative: use a queue, swap children at each node during level-order traversal. Same result, different traversal order.

4

Edge cases: empty tree (return null), single node (return as-is), already inverted (same result).

Optimal Approach

Recursive DFS:
Step 1: Base case — if root is null, return null.
Step 2: Swap root.left and root.right.
Step 3: Recursively invert root.left and root.right.
Step 4: Return root.

The swap happens before recursion, so the entire subtree is inverted as we unwind.

Time: O(n) — visit every node once. Space: O(h) — recursion stack.

Swap first, then recurse

1234swap 2 and 7679Step 1 — at the root, exchange left and right97swap 6 and 96432swap 1 and 31Step 2 — recurse into both children and swap there as wellif root is null: return nullswap root.left and root.rightinvertTree(left); invertTree(right)return root
At each node we swap its two children, then repeat the same step on both subtrees.
ComplexityTime O(n)Space O(h)Each node is visited once, and the extra space is the recursion stack, whose depth is the tree height h (O(n) in the worst case of a skewed tree).

What Trips People Up in Real Interviews

1

Not handling the base case. If the node is null, return null. Without this, you'll get a null pointer exception.

2

Forgetting to recurse after swapping. You need to swap children AND then invert both subtrees.

3

Confusing "invert" with "mirror image." Inverting a binary tree means every left child becomes right and vice versa. The result is a mirror image.

4

Not handling a single node. A single node tree is already inverted — just return it.

5

Trying to invert by traversing and building a new tree. The problem says to invert in-place by swapping children. Don't create new nodes — just swap existing left and right pointers.

Solution Code

O(n) time
def invertTree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Invert Binary Tree problem?

Given the root of a binary tree, invert the tree and return its root. Inverting means swapping every left and right child recursively. Made famous by the "would you invert a binary tree?" meme.

How do you solve Invert Binary Tree?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Invert Binary Tree?

Invert Binary Tree is asked at Google, Meta, Amazon, Microsoft, Apple. It is a easy difficulty problem.

What are common mistakes on Invert Binary Tree?
  • Not handling the base case. If the node is `null`, return `null`. Without this, you'll get a `null` pointer exception.
  • Forgetting to recurse after swapping. You need to swap children AND then invert both subtrees.
  • Confusing "invert" with "mirror image." Inverting a binary tree means every left child becomes right and vice versa. The result is a mirror image.
  • Not handling a single node. A single node tree is already inverted — just return it.
  • Trying to invert by traversing and building a new tree. The problem says to invert in-place by swapping children. Don't create new nodes — just swap existing left and right pointers.