Invert Binary Tree

Difficulty: Easy Source: NeetCode

Problem

Given the root of a binary tree, invert the tree, and return its root.

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

Example 2: Input: root = [2,1,3] Output: [2,3,1]

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Binary Trees — Understanding the parent-child relationship between nodes
• Recursion — Applying the same operation to smaller subproblems
• BFS / Queue — Level-by-level traversal used in the iterative approach

1. Recursive DFS

Intuition

To invert a tree, swap the left and right children at each node, then recursively invert both subtrees. The order of the recursion vs. the swap doesn’t matter — swap first or recurse first both work.

Algorithm

1. If the current node is null, return null
2. Swap node.left and node.right
3. Recursively invert node.left
4. Recursively invert node.right
5. Return the node

Solution

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

def invert_tree_recursive(root):
    if not root:
        return None

    # Swap children
    root.left, root.right = root.right, root.left

    # Recurse into each subtree
    invert_tree_recursive(root.left)
    invert_tree_recursive(root.right)

    return root

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

def level_order(root):
    """Return level-order list for easy visualization."""
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

# --- tests ---
root1 = build_tree([4, 2, 7, 1, 3, 6, 9])
invert_tree_recursive(root1)
print(level_order(root1))  # [4, 7, 2, 9, 6, 3, 1]

root2 = build_tree([2, 1, 3])
invert_tree_recursive(root2)
print(level_order(root2))  # [2, 3, 1]

Complexity

• Time: O(n) — every node is visited once
• Space: O(h) — recursion depth proportional to tree height

2. Iterative (BFS with Queue)

Intuition

We can do the same thing level by level using a queue. For each node we dequeue, swap its children and enqueue those children to process later.

Algorithm

1. Initialize a queue with the root
2. While the queue is not empty:
   • Dequeue a node
   • Swap its left and right children
   • Enqueue non-null children
3. Return the root

Solution

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 invert_tree_iterative(root):
    if not root:
        return None

    queue = deque([root])

    while queue:
        node = queue.popleft()
        # Swap children
        node.left, node.right = node.right, node.left
        # Enqueue children for processing
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return root

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

def level_order(root):
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

# --- tests ---
root1 = build_tree([4, 2, 7, 1, 3, 6, 9])
invert_tree_iterative(root1)
print(level_order(root1))  # [4, 7, 2, 9, 6, 3, 1]

root2 = build_tree([2, 1, 3])
invert_tree_iterative(root2)
print(level_order(root2))  # [2, 3, 1]

Complexity

• Time: O(n) — every node is processed once
• Space: O(w) — queue holds at most the widest level of the tree

Common Pitfalls

Forgetting to return the root. The problem asks you to return the root of the inverted tree. After all the swaps, the root is the same node — just return it.

Confusing inversion with reversal. Inverting a binary tree swaps left and right children at every level — it’s a mirror image. It’s not the same as reversing the values in the tree.