Invert Binary Tree

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]

Example 3:

Input: root = []
Output: []

Constraints:

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

Solution

Approach 1: Recursive DFS

The key insight is that inverting a tree means swapping left and right children at every node, then recursively inverting the subtrees.

Implementation

# 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 not root:
            return None

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

        # Recursively invert subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Approach 2: Iterative BFS

Use a queue to process nodes level by level, swapping children at each node.

from collections import deque

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        queue = deque([root])

        while queue:
            node = queue.popleft()

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

            # Add children to queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return root

Complexity Analysis

Recursive:

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(h), where h is the height of the tree. This is the recursion stack space.

Iterative:

Time Complexity: O(n), we visit each node once.
Space Complexity: O(w), where w is the maximum width of the tree (for the queue).

Key Insights

Simple Swap: Inverting a tree is conceptually simple - just swap left and right children at every node.
Recursive Structure: Trees have natural recursive structure. Inverting a tree = swap children + invert left subtree + invert right subtree.
Order Doesn’t Matter: We can swap first then recurse, or recurse first then swap. Both work because we’re doing the same operation at every node.
DFS vs BFS: Both traversal approaches work. DFS (recursive) is more concise. BFS (iterative) uses a queue and processes level by level.
In-Place Modification: We modify the tree in place by swapping pointers. No new nodes are created.