Problem Statement

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

Inverting a binary tree means swapping the left and right children of every single node in the tree.

Additional information

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

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: []

Depth-First Search (Recursive)

Intuition

The problem asks us to swap the left and right children of every node. Since a tree is a recursive data structure, we can solve this recursively.

For any given root node, we first swap its direct left and right children. Once the current node's children are swapped, we recursively call the same function on the left child and the right child to invert their respective subtrees.

Algorithm

1. Base Case: If the root is None, we have reached the bottom of a branch or an empty tree. Return None.
2. Swap: Store root.left in a temporary variable, assign root.right to root.left, and assign the temporary variable to root.right.
3. Recurse: Call invert_tree(root.left) and invert_tree(root.right).
4. Return: Return the root node.

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
        
    # Swap the children
    root.left, root.right = root.right, root.left
    
    # Recursively invert the subtrees
    invert_tree(root.left)
    invert_tree(root.right)
    
    return root

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node in the binary tree exactly once.

• Space complexity: O(h)

• Reason: The space complexity is determined by the height h of the tree due to the recursion stack. In the worst case (a perfectly skewed tree), this is O(n). In the best case (a balanced tree), it is O(log n).

Breadth-First Search (Iterative)

Intuition

If we want to avoid recursion (and the potential stack overflow for very deep trees), we can use an iterative Breadth-First Search (BFS) approach using a Queue.

We process the tree level by level. We pop a node from the queue, swap its left and right children, and then push its non-null children into the queue to be processed later.

Algorithm

1. If the root is None, return None.
2. Initialize a queue (using a standard list or collections.deque) and append the root node.
3. While the queue is not empty:

• Pop the first node from the queue (curr).
• Swap curr.left and curr.right.
• If curr.left is not None, append it to the queue.
• If curr.right is not None, append it to the queue.

4. Return the original root.

from collections import deque

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
        
    queue = deque([root])
    
    while queue:
        curr = queue.popleft()
        
        # Swap the children
        curr.left, curr.right = curr.right, curr.left
        
        # Add children to queue to process them later
        if curr.left:
            queue.append(curr.left)
        if curr.right:
            queue.append(curr.right)
            
    return root

Time & Space Complexity

• Time complexity: O(n)

• Reason: Every node is pushed and popped from the queue exactly once.

• Space complexity: O(n)

• Reason: In the worst case (a full binary tree), the queue will hold all the leaf nodes at the bottom level, which is roughly n/2 nodes, resulting in O(n) space.