Binary Tree problems are a staple in coding interviews, and Invert Binary Tree is one of the most famous ones. Despite its simplicity, this problem is an excellent exercise for understanding tree traversal and the differences between recursive DFS, iterative DFS, and BFS.

Problem Statement

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

Example

Input:
        1
      /   \
     2     3
    / \   / \
   4   5 6   7

Output:
        1
      /   \
     3     2
    / \   / \
   7   6 5   4

The goal is simple: swap the left and right child of every node in the tree.

Key Observation

Each node only requires one operation:

Swap its left and right children.
Repeat the same process for both subtrees.

Since every node must be visited exactly once, all valid solutions will have a time complexity of O(n), where n is the number of nodes.

Solution 1: Recursive DFS

The recursive solution is the most natural approach.

Idea

For every node:

Swap its children.
Recursively invert the left subtree.
Recursively invert the right subtree.

class Solution:
    def invertTree(self, root):
        if not root:
            return None

        tmp = root.left
        root.left = root.right
        root.right = tmp

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Walkthrough

Consider the tree:

      4
     / \
    2   7

First call:

Swap 2 and 7

      4
     / \
    7   2

Then recursively process:

subtree rooted at 7
subtree rooted at 2

Eventually every node gets swapped.

Complexity

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

where h is the height of the tree.

Balanced tree: O(log n)
Skewed tree: O(n)

Pros

Very clean
Easy to understand
Matches the recursive nature of trees

Cons

Uses recursion stack
Deep trees could cause stack overflow in some languages

Solution 2: Iterative DFS (Using a Stack)

If recursion is not preferred, we can simulate DFS with an explicit stack.

Idea

Push the root onto the stack.
Pop a node.
Swap its children.
Push its children back onto the stack.

class Solution:
    def invertTree(self, root):
        if not root:
            return None

        stack = [root]

        while stack:
            node = stack.pop()

            tmp = node.left
            node.left = node.right
            node.right = tmp

            if node.left:
                stack.append(node.left)

            if node.right:
                stack.append(node.right)

        return root

Why it Works

The stack processes nodes in Depth-First Search (DFS) order.

For example:

Stack:

[1]

Pop 1
Swap children
Push 3
Push 2

Stack:
[3,2]

The traversal continues until every node has been processed.

Complexity

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

where h is the maximum depth of the tree.

Solution 3: Breadth-First Search (Queue)

Instead of exploring one branch deeply, we can process the tree level by level.

Idea

Start with the root.
Pop one node from the queue.
Swap its children.
Push both children into the queue.

from collections import deque

class Solution:
    def invertTree(self, root):
        if not root:
            return None

        queue = deque([root])

        while queue:
            node = queue.popleft()

            tmp = node.left
            node.left = node.right
            node.right = tmp

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        return root

Why it Works

The queue performs Breadth-First Search (BFS).

Processing order:

Level 1:
    1

Level 2:
   2   3

Level 3:
 4 5 6 7

Each node swaps its children before moving to the next level.

Complexity

Time: O(n)
Space: O(w)

where w is the maximum width of the tree.

In a balanced tree, the queue can hold approximately n/2 nodes, giving a worst-case space complexity of O(n).

DFS vs BFS

Approach	Data Structure	Space Complexity	Notes
Recursive DFS	Call Stack	O(h)	Cleanest solution
Iterative DFS	Stack	O(h)	Avoids recursion
BFS	Queue	O(w)	Processes level by level

All three approaches visit every node exactly once, so they all have:

Time Complexity: O(n)

The primary difference is how nodes are stored while traversing the tree.

Why Swap Before Traversing?

A common question is whether we should swap first or recurse first.

Both approaches work because every node is eventually visited exactly once.

For example:

swap(root)

invert(left)

invert(right)

invert(left)

invert(right)

swap(root)

Both correctly invert the tree since swapping only affects the current node’s immediate children.

Edge Cases

Empty tree ([])
Single-node tree
Completely skewed tree
Perfect binary tree

All three solutions handle these cases correctly.

Final Thoughts

Invert Binary Tree is less about the swapping itself and more about understanding tree traversal.

The recursive solution is the most elegant and is usually the preferred interview answer because it mirrors the recursive structure of trees.

However, knowing how to solve the problem iteratively using DFS with a stack and BFS with a queue demonstrates a deeper understanding of traversal techniques and prepares you for scenarios where recursion may not be ideal.

Whenever you encounter a tree problem, ask yourself:

Can recursion solve it naturally?
Can I simulate recursion using a stack?
Would processing level by level with a queue make the problem easier?

Recognizing these traversal patterns is a key step toward mastering binary tree problems.

Subscribe to Sharooq

Subscribe to Sharooq