How do you write a function to invert a binary tree in your programming language of choice?

Question Analysis

The question asks you to write a function that inverts a binary tree. Inverting a binary tree means swapping the left and right children of all nodes in the tree. This is a common problem that tests your understanding of binary tree structures and your ability to manipulate them using recursion or iteration. The problem is typically solved using a recursive approach, but an iterative approach using a queue or stack is also possible.

Answer

To invert a binary tree, you can use a recursive approach, which is straightforward and easy to understand. Here is a sample implementation in Python:

# 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

def invertTree(root: TreeNode) -> TreeNode:
    if root is None:
        return None
    
    # Recursively invert the left and right subtrees
    left_inverted = invertTree(root.left)
    right_inverted = invertTree(root.right)
    
    # Swap the left and right children
    root.left = right_inverted
    root.right = left_inverted
    
    return root

Explanation:

• Base Case: If the current node (root) is None, return None. This handles the leaf nodes and the case when the tree is empty.
• Recursive Case: For each node, recursively invert its left and right subtrees.
• After inverting the subtrees, swap the left and right children of the current node.
• Finally, return the root of the inverted tree.

This approach effectively traverses the tree in a post-order manner (processing children before the node itself) and inverts each subtree, achieving the desired result.