226. Invert Binary Tree (Easy)

Problem

Given the root of a binary tree, invert the tree and return its root. Inverting swaps the left and right children at every node.

Example

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

LeetCode 226 · Link · Easy

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive DFS (canonical)

Swap children at the current node, then recurse into each subtree.

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

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)  # L1: swap + recurse
    return root

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

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];  // L1: swap + recurse
    return root;
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = invertTree(root.Right), invertTree(root.Left) // L1: swap + recurse
    return root
}

final class Solution { func invertTree(_ root: TreeNode?) -> TreeNode? { guard let root else { return nil }; let left = invertTree(root.left); root.left = invertTree(root.right); root.right = left; return root } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L1 (swap + two recursive calls)	$O(1)$ per node	n	$O(n)$ ← dominates

Every node triggers exactly one swap and two recursive calls. No node is visited more than once.

Complexity

Time: $O(n)$ , driven by L1 visiting each node once.
Space: $O(h)$ recursion depth ( $O(log n)$ balanced, $O(n)$ skewed).

The one-liner swap is the canonical interview answer.

Approach 2: Iterative BFS with a queue

Level-order walk, swapping children at each popped node.

from collections import deque

def invert_tree(root):
    if not root:
        return None
    q = deque([root])             # L1: O(1) init
    while q:
        node = q.popleft()        # L2: O(1) dequeue
        node.left, node.right = node.right, node.left  # L3: O(1) swap
        if node.left:
            q.append(node.left)   # L4: O(1) enqueue
        if node.right:
            q.append(node.right)  # L5: O(1) enqueue
    return root

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const q: TreeNode[] = [root];             // L1: O(1) init
    while (q.length) {
        const node = q.shift()!;              // L2: O(1) dequeue
        [node.left, node.right] = [node.right, node.left];  // L3: O(1) swap
        if (node.left) q.push(node.left);     // L4: O(1) enqueue
        if (node.right) q.push(node.right);   // L5: O(1) enqueue
    }
    return root;
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    q := []*TreeNode{root}             // L1: O(1) init
    for len(q) > 0 {
        node := q[0]
        q = q[1:]                      // L2: O(1) dequeue
        node.Left, node.Right = node.Right, node.Left  // L3: O(1) swap
        if node.Left != nil {
            q = append(q, node.Left)   // L4: O(1) enqueue
        }
        if node.Right != nil {
            q = append(q, node.Right)  // L5: O(1) enqueue
        }
    }
    return root
}

final class Solution { func invertTree(_ root: TreeNode?) -> TreeNode? { guard let root else { return nil }; var queue = [root], read = 0; while read < queue.count { let node = queue[read]; read += 1; let left = node.left; node.left = node.right; node.right = left; if let left = node.left { queue.append(left) }; if let right = node.right { queue.append(right) } }; return root } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L2 (dequeue)	$O(1)$	n	$O(n)$
L3 (swap)	$O(1)$	n	$O(n)$
L4/L5 (enqueue)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Complexity

Time: $O(n)$ .
Space: $O(w)$ , max width of the tree.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Iterative DFS with a stack

Same as BFS but with a LIFO stack instead of a FIFO queue.

Python
Swift

def invert_tree(root):
    if not root:
        return None
    stack = [root]              # L1: O(1) init
    while stack:
        node = stack.pop()      # L2: O(1) pop
        node.left, node.right = node.right, node.left  # L3: O(1) swap
        if node.left:
            stack.append(node.left)   # L4: O(1) push
        if node.right:
            stack.append(node.right)  # L5: O(1) push
    return root

final class Solution { func invertTree(_ root: TreeNode?) -> TreeNode? { guard let root else { return nil }; var stack = [root]; while let node = stack.popLast() { let left = node.left; node.left = node.right; node.right = left; if let left = node.left { stack.append(left) }; if let right = node.right { stack.append(right) } }; return root } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L2 (pop)	$O(1)$	n	$O(n)$
L3 (swap)	$O(1)$	n	$O(n)$
L4/L5 (push)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Complexity

Time: $O(n)$ .
Space: $O(h)$ .

Summary

Approach	Time	Space
Recursive DFS	$O(n)$	$O(h)$
Iterative BFS	$O(n)$	$O(w)$
Iterative DFS	$O(n)$	$O(h)$

All three are optimal in time. The recursive one-liner is the canonical answer; the iterative variants are useful when recursion depth is a concern on skewed trees.

from collections import deque

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result, q = [], deque([root])
    while q:
        node = q.popleft()
        if node:
            result.append(node.val)
            q.append(node.left)
            q.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

def _run_tests():
    assert tree_to_list(invert_tree(build_tree([4, 2, 7, 1, 3, 6, 9]))) == [4, 7, 2, 9, 6, 3, 1]
    assert invert_tree(None) is None
    assert tree_to_list(invert_tree(build_tree([1]))) == [1]
    # invert twice = original
    t = build_tree([1, 2, 3])
    assert tree_to_list(invert_tree(invert_tree(t))) == [1, 2, 3]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

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

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function treeToList(root: TreeNode | null): (number | null)[] {
    if (!root) return [];
    const result: (number | null)[] = [];
    const q: (TreeNode | null)[] = [root];
    while (q.length) {
        const node = q.shift()!;
        if (node) { result.push(node.val); q.push(node.left); q.push(node.right); }
        else result.push(null);
    }
    while (result.length && result[result.length - 1] === null) result.pop();
    return result;
}

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
    return root;
}

console.assert(JSON.stringify(treeToList(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9])))) === JSON.stringify([4, 7, 2, 9, 6, 3, 1]));
console.assert(invertTree(null) === null);
console.assert(JSON.stringify(treeToList(invertTree(buildTree([1])))) === JSON.stringify([1]));
console.log("all tests pass");

Binary Trees & BSTs, subtree recursion mirror

Recursion, self-similar problem-solving tactics for trees, divide-and-conquer, and search branches.
Tree Traversal, recursive and iterative tactics for visiting tree nodes with path, depth, or structural state.

226. Invert Binary Tree (Easy)

Problem

Try it yourself

Approach 1: Recursive DFS (canonical)

Approach 2: Iterative BFS with a queue

Approach 3: Iterative DFS with a stack

Summary

Test cases

Related data structures

Related concepts