What is the brute force approach and complexity for Invert Binary Tree?

Walk the tree with BFS and swap each node's children when it is popped with time complexity O(N) and space complexity O(W).

What is the optimal approach and complexity for Invert Binary Tree?

Invert the left and right subtrees first, then put them into swapped slots with optimal time complexity O(N) and space complexity O(H).

How do you identify the pattern for Invert Binary Tree?

Look for key signals in the prompt: "swap left and right at every node" indicates Every node gets the same small local change, so one recursive rule can cover the whole tree.; "return the root" indicates The root stays the same node. Only its children move, so the answer is the tree we started with.; "binary tree" indicates Each child is the root of a smaller tree, so the recursion can treat each subtree as a smaller problem..

Invert Binary Tree

Easy·LeetCode #226Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree DFS (transform, bottom-up)

Complexity:O(N)→O(N)

Key Insight

Invert the left subtree, invert the right subtree, then put the results into swapped slots. Each subtree is the same kind of problem, so the recursion handles every level. The swap happens after both children are finished, so no pointer is read after it has been overwritten.

Core Validity Invariant

The tree is inverted when every node has its two children swapped, and each call makes that true for its own node after its subtrees are already done.

Problem

You are given the root of a binary tree. Flip the whole tree like a mirror: at every node, its left child and its right child swap places.

Return the root of the flipped tree. The root itself stays the same node. Only the children move.

Input

The root of a binary tree. The tree can be empty.

Output

The same root, after every node's two children have been swapped.

Example 1

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

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

Node 4 swaps its children, so 7 comes first. Node 7 swaps 6 and 9, and node 2 swaps 1 and 3. Leaves have nothing to swap.

Example 2

Input: root = [2, 1, 3]

Output: [2, 3, 1]

Only the root has children, so 1 and 3 swap.

Example 3

Input: root = []

Output: []

An empty tree stays empty.

Constraints

• 0 ≤ number of nodes ≤ 100
• −100 ≤ Node.val ≤ 100

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I only swap the children of the root, what is still wrong with the tree?
2.
Does swapping at a node also change the shape of the subtrees below it?
3.
Can I finish the children first and then swap at the parent? Does the order I visit nodes matter?
4.
If I use a queue, which nodes must I reach, and in what order?
5.
What should happen when a node has one child, or no children at all?

Brute force approach

Idea

Walk the tree level by level with a queue, the way you would print it. When a node comes off the queue, swap its two children, then queue them so they get swapped too. Every node is popped once, so every node is swapped once.

Thinking process

1
Inverting means every node swaps its two children, so I need to reach every node once.
2
BFS reaches every node. Start with the root in the queue.
3
On [4,2,7,1,3,6,9]: pop 4 and swap its children, so 7 is now on the left. Queue 7, then 2. Pop 7 and swap 6 and 9 into 9, 6. Pop 2 and swap 1 and 3 into 3, 1.
4
The leaves (1, 3, 6, 9) are popped too, but they have no children to swap.
5
An empty tree gives an empty queue, so nothing runs and the function returns null.

Visual

The queue runs front (left) to back (right). Green = already swapped, blue = popped now. Leaves are popped too, but have no children to swap.

BFS swaps level by levelroot = [4, 2, 7, 1, 3, 6, 9]step 1/14

queue

▲front

Pop

popped: 4
queue after pop: empty

Pop 4

Pop 4 from the front of the queue. Its children are still the old ones, so we swap them next.

Code & Implementation

brute.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        // Go level by level. Swap the two children of each node as we pop it.
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            swap(node->left, node->right);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return root;
    }
};

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

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;
        // Go level by level. Swap the two children of each node as we pop it.
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        return root;
    }
}

from collections import deque
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        # Go level by level. Swap the two children of each node as we pop it.
        q = deque([root])
        while q:
            node = q.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return root

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    // Go level by level. Swap the two children of each node as we pop it.
    const q: TreeNode[] = [root];
    while (q.length > 0) {
        const node = q.shift()!;
        const temp = node.left;
        node.left = node.right;
        node.right = temp;
        if (node.left) q.push(node.left);
        if (node.right) q.push(node.right);
    }
    return root;
}

Complexity

Time O(N)Space O(W)

Same O(n) time as the recursion, because every node is popped and swapped once. The only difference is space: the queue holds one level, so it uses O(W), where W is the widest level. The recursion uses O(H), the tree height. Neither is always smaller. A chain has H = n but W = 1, while a full tree has H = log n but W = n/2. The recursion is shorter to write, so it is the usual answer.

Optimized approach

Idea

Start from brute force

Brute force walks level by level and keeps the next nodes in a queue. The recursion walks down one path first and swaps each node on the way back up.

Find the repeated work

There is no repeated work to remove, because both approaches touch every node once. What changes is memory: the queue holds a whole level, while the recursion holds only the current path.

Define the state — what variables do I need?

root: The node this call works on. It is the same node before and after, because only its children move.
left: The root returned by inverting the left subtree. It is the node that will go on the right.
right: The root returned by inverting the right subtree. It is the node that will go on the left.

Define validity

The tree is inverted when every node has its two children swapped, and each call makes that true for its own node after its subtrees are already done.

Define the transitions — when does each pointer move, and why is it safe?

Base case: root is null

return null

An empty subtree has nothing to swap.

After both recursive calls return

root->left = right; root->right = left; return root;

Both results were saved in variables first. Nothing is read after it has been overwritten.

What does the current window add to the answer?

Each call adds one swap at its node. Every node is inside exactly one call, so every node is swapped exactly once.

Code & Implementation

optimal.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        // invertTree works in place and returns the node it was given,
        // so these are just the two children. Save both before we overwrite anything.
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

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;
        // invertTree works in place and returns the node it was given,
        // so these are just the two children. Save both before we overwrite anything.
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        # invertTree works in place and returns the node it was given,
        # so these are just the two children. Save both before we overwrite anything.
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    // invertTree works in place and returns the node it was given,
    // so these are just the two children. Save both before we overwrite anything.
    const left = invertTree(root.left);
    const right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

Complexity

Time O(N)Space O(H)

Same O(n) time as the brute force. The recursion keeps O(H) call frames instead of a queue of width W, so it is smaller on bushy trees (a full tree has W about n/2 but H about log n). On a chain it is the other way round: H = n and W = 1.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Walk the tree with BFS and swap each node's children when it is popped	O(N)	O(W)
Optimal	Invert the left and right subtrees first, then put them into swapped slots	O(N)	O(H)

Why does this belong to this pattern?

Clues in the problem statement

“swap left and right at every node”Every node gets the same small local change, so one recursive rule can cover the whole tree.
“return the root”The root stays the same node. Only its children move, so the answer is the tree we started with.
“binary tree”Each child is the root of a smaller tree, so the recursion can treat each subtree as a smaller problem.

Visit every node once+Swap two pointers at each node+Root stays the same→Tree DFS (transform, bottom-up)

This is the anchor of the transform sub-pattern. The change at each node is one swap, so the only thing that matters is when you read the pointers. The later problems in this group (flatten, build, serialize) also use a tree DFS, but they relink pointers, so the visit order matters even more.

Don't make this mistake

Overwriting the left child before reading it

✗ root->left = invertTree(root->right); root->right = invertTree(root->left);

✓ TreeNode* left = invertTree(root->left); TreeNode* right = invertTree(root->right); root->left = right; root->right = left;

The first line overwrites root->left, so the second line inverts the wrong node. On [4,2,7,1,3,6,9], the first line puts node 7 on the left, which drops node 2 and its children. The second line inverts that same node 7 again and writes it to the right. Node 7 is now shared by both sides, and the output is [4,7,7,9,9,9,9] instead of [4,7,2,9,6,3,1].

Reversing the level-order array

The LeetCode input looks like a list, so it is tempting to reverse it. That does not invert the tree. For [4,2,7,1,3,6,9] the reversed list is [9,6,3,1,7,2,4], which is not the answer. Inverting moves each node's children, not the positions in the list.

Forgetting the empty-child base case

✗ void invert(TreeNode* root) { swap(root->left, root->right); invert(root->left); invert(root->right); }

✓ void invert(TreeNode* root) { if (!root) return; swap(root->left, root->right); invert(root->left); invert(root->right); }

A leaf has two null children. The call on a null child then reads root->left on a null pointer, so the program crashes on the first leaf. Check for null before you touch the node.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture