Invert Binary Tree

Difficulty: Easy | Acceptance: 80.00% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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

• Examples
• Constraints
• Recursive Depth-First Search
• Iterative Depth-First Search
• Breadth-First Search

Examples

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

Recursive Depth-First Search

Intuition We traverse the tree using a pre-order approach. For every node visited, we swap its left and right children, then recursively apply the same operation to the subtrees.

Steps

• Base case: If the root is null, return null.
• Swap the left and right children of the current node.
• Recursively call the function on the left subtree.
• Recursively call the function on the right subtree.
• Return the root.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        # Swap the children
        root.left, root.right = root.right, root.left
        
        # Recurse on the subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root

Complexity

• Time: O(n) where n is the number of nodes in the tree, as we visit each node once.
• Space: O(h) where h is the height of the tree. This represents the depth of the recursion stack. In the worst case (skewed tree), this is O(n).
• Notes: This is the most intuitive solution and mimics the definition of the problem directly.

Iterative Depth-First Search

Intuition We can simulate the recursive approach using an explicit stack data structure. We push nodes onto the stack, pop them, swap their children, and push the children onto the stack for processing.

Steps

• Initialize a stack and push the root node onto it.
• While the stack is not empty:
  • Pop a node from the stack.
  • If the node is not null:
    • Swap its left and right children.
    • Push the left child onto the stack.
    • Push the right child onto the stack.
• Return the root.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                # Swap children
                node.left, node.right = node.right, node.left
                # Push children to stack
                stack.append(node.left)
                stack.append(node.right)
        
        return root

Complexity

• Time: O(n) as we process each node exactly once.
• Space: O(n) in the worst case, as the stack might grow to the size of the tree (e.g., for a skewed tree).
• Notes: This avoids recursion stack overflow issues for very deep trees, though Python’s recursion limit is usually sufficient for the given constraints.

Breadth-First Search

Intuition We process the tree level by level using a queue. For each node dequeued, we swap its children and enqueue them for subsequent processing.

Steps

• Initialize a queue and enqueue the root node.
• While the queue is not empty:
  • Dequeue a node.
  • If the node is not null:
    • Swap its left and right children.
    • Enqueue the left child.
    • Enqueue the right child.
• Return the root.

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()
            if node:
                # Swap children
                node.left, node.right = node.right, node.left
                # Enqueue children
                queue.append(node.left)
                queue.append(node.right)
        
        return root

Complexity

• Time: O(n) as we visit each node once.
• Space: O(n) to store the nodes in the queue. In the worst case (a complete binary tree), the maximum size of the queue is roughly the width of the tree, which is O(n).
• Notes: This approach is useful if you want to process nodes level by level, though for this specific problem, DFS is often slightly more memory efficient due to stack depth vs queue width.