LeetCode 226 - Invert Binary Tree

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives the root node of a binary tree and asks us to invert the tree. Inverting a binary tree means swapping the left and right child of every node in the tree.

For example, if a node originally has:

left child = 2
right child = 7

after inversion it becomes:

left child = 7
right child = 2

This operation must be performed for every node in the tree, not just the root.

The input is represented as a binary tree. Each node contains:

an integer value
a pointer/reference to a left child
a pointer/reference to a right child

The output should be the root of the modified tree after all left and right children have been swapped recursively.

The constraints are small:

The tree contains between 0 and 100 nodes.
Node values range from -100 to 100.

Since the tree size is small, performance is not a major concern. Even an O(n) traversal is more than fast enough. The important part is correctly traversing every node exactly once and swapping its children.

Several edge cases are important:

An empty tree (root = []) should return None or nil.
A tree with only one node should remain unchanged.
Highly unbalanced trees, such as linked-list-shaped trees, must still work correctly.
Recursive solutions must handle None child pointers safely.

The problem guarantees that the input is a valid binary tree, so we do not need to validate tree structure or handle cycles.

Approaches

Brute Force Approach

A brute-force way to think about this problem is to create an entirely new tree. For every node in the original tree, we could create a corresponding node in the new tree where:

the new node's left child is built from the original node's right subtree
the new node's right child is built from the original node's left subtree

This produces a fully inverted copy of the original tree.

This approach is correct because every subtree is reconstructed with its children reversed. However, it requires allocating a completely new tree, which uses unnecessary extra memory. Since the problem allows modifying the existing tree in place, creating a duplicate tree is inefficient.

Optimal Approach

The key observation is that inversion is purely a local operation. At every node, we only need to swap two pointers:

left
right

After swapping them, we recursively invert both subtrees.

Because every node is visited exactly once and each swap takes constant time, the algorithm runs efficiently in linear time.

This naturally fits a Depth-First Search traversal. Recursion is especially clean here because binary trees are recursively defined structures. The inversion of the entire tree depends on inverting its left and right subtrees.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Builds an entirely new inverted tree
Optimal	O(n)	O(h)	Swaps children in place using DFS recursion

Here:

n is the number of nodes
h is the height of the tree

Algorithm Walkthrough

Recursive DFS Algorithm

Start at the root node.

The root is the entry point into the tree. If the root is None, the tree is empty, so we immediately return None. 2. Swap the left and right child pointers of the current node.

This is the core inversion step. After the swap:

the original left subtree becomes the right subtree
the original right subtree becomes the left subtree

Recursively invert the new left subtree.

After swapping, the node's current left child was originally the right subtree. We recursively apply the same inversion process to it. 4. Recursively invert the new right subtree.

We then recursively process the other subtree. 5. Return the current node.

Once both subtrees are inverted, the subtree rooted at the current node is fully inverted.

Why it works

The algorithm works because inversion is independent at each node. If every node swaps its left and right children exactly once, then the entire tree becomes mirrored.

The recursive invariant is:

When invertTree(node) finishes, the subtree rooted at node is fully inverted.

The base case handles empty subtrees correctly, and the recursive calls ensure every subtree is processed completely.

Python Solution

# Definition for a binary tree node.
# 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 root is None:
            return None

        root.left, root.right = root.right, root.left

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

        return root

The implementation starts with the base case. If root is None, there is no subtree to invert, so the function returns immediately.

The next line performs the actual inversion step:

root.left, root.right = root.right, root.left

Python tuple assignment makes swapping concise and safe.

After the swap, the function recursively processes both subtrees. Because the children have already been exchanged, the recursive calls operate on the newly positioned subtrees.

Finally, the root node is returned. Since the inversion happens in place, returning the same root reference is sufficient.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    root.Left, root.Right = root.Right, root.Left

    invertTree(root.Left)
    invertTree(root.Right)

    return root
}

The Go implementation follows the exact same recursive logic as the Python version.

The main difference is handling nil pointers instead of Python's None. Go also uses explicit struct pointers for tree nodes.

Tuple assignment is supported in Go as well:

root.Left, root.Right = root.Right, root.Left

This makes the swap operation concise and avoids needing a temporary variable.

Because the node count is small, recursion depth is not a concern for this problem.

Worked Examples

Example 1

Input:

        4
      /   \
     2     7
    / \   / \
   1   3 6   9

We start at node 4.

Current Node	Left Child	Right Child	After Swap
4	2	7	left=7, right=2

Tree becomes:

        4
      /   \
     7     2
    / \   / \
   6   9 1   3

Now recursively process node 7.

Current Node	Left Child	Right Child	After Swap
7	6	9	left=9, right=6

Process node 2.

Current Node	Left Child	Right Child	After Swap
2	1	3	left=3, right=1

Leaf nodes (1, 3, 6, 9) simply swap None children with None, so they remain unchanged.

Final tree:

        4
      /   \
     7     2
    / \   / \
   9   6 3   1

Output:

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

Example 2

Input:

    2
   / \
  1   3

Swap children of node 2.

Current Node	Left Child	Right Child	After Swap
2	1	3	left=3, right=1

Final tree:

    2
   / \
  3   1

Output:

[2,3,1]

Example 3

Input:

[]

The root is None, so the function immediately returns None.

Output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack stores at most one path from root to leaf

The time complexity is linear because each node performs only a constant amount of work:

one swap
two recursive calls

The space complexity depends on recursion depth. In a balanced tree, the height is O(log n). In the worst case, a completely skewed tree has height O(n).

Test Cases

# Helper functions for testing

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):
        if root is None:
            return None

        root.left, root.right = root.right, root.left

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

        return root

def tree_to_list(root):
    if not root:
        return []

    result = []
    queue = [root]

    while queue:
        node = queue.pop(0)

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

# Test 1: Example 1
root = TreeNode(
    4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(7, TreeNode(6), TreeNode(9))
)
assert tree_to_list(Solution().invertTree(root)) == [4, 7, 2, 9, 6, 3, 1]  # balanced tree

# Test 2: Example 2
root = TreeNode(2, TreeNode(1), TreeNode(3))
assert tree_to_list(Solution().invertTree(root)) == [2, 3, 1]  # simple 3-node tree

# Test 3: Empty tree
assert Solution().invertTree(None) is None  # empty input

# Test 4: Single node
root = TreeNode(1)
assert tree_to_list(Solution().invertTree(root)) == [1]  # no children to swap

# Test 5: Left-skewed tree
root = TreeNode(1, TreeNode(2, TreeNode(3)))
assert tree_to_list(Solution().invertTree(root)) == [1, None, 2, None, 3]  # becomes right-skewed

# Test 6: Right-skewed tree
root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
assert tree_to_list(Solution().invertTree(root)) == [1, 2, None, 3]  # becomes left-skewed

# Test 7: Tree with negative values
root = TreeNode(-1, TreeNode(-2), TreeNode(-3))
assert tree_to_list(Solution().invertTree(root)) == [-1, -3, -2]  # negative numbers

# Test 8: Already symmetric tree
root = TreeNode(1, TreeNode(2), TreeNode(2))
assert tree_to_list(Solution().invertTree(root)) == [1, 2, 2]  # structure remains symmetric

Test	Why
Balanced binary tree	Validates standard recursive inversion
Small 3-node tree	Confirms basic swap behavior
Empty tree	Ensures base case works correctly
Single node	Confirms no unnecessary modifications
Left-skewed tree	Tests deeply unbalanced structure
Right-skewed tree	Verifies inversion direction correctness
Negative values	Confirms values do not affect logic
Symmetric tree	Ensures algorithm still processes all nodes

Edge Cases

Empty Tree

An empty tree is represented by root = None. This is the simplest edge case and is easy to mishandle if recursion assumes a valid node always exists.

Without a proper base case, attempting to access root.left or root.right would cause a runtime error.

The implementation handles this immediately:

if root is None:
    return None

This safely terminates recursion for empty subtrees as well.

Single Node Tree

A tree with exactly one node has no children to swap.

A buggy implementation might accidentally modify pointers incorrectly or recurse unnecessarily.

In this solution, the node's children are both None, so swapping them changes nothing. The recursive calls immediately terminate because both children are None.

Highly Unbalanced Tree

A skewed tree behaves like a linked list:

These cases are important because recursion depth becomes equal to tree height.

The algorithm still works correctly because each node independently swaps its children. After inversion, the above tree becomes:

The implementation naturally handles this because recursion follows whichever child exists.