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 to invert 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 in coding interviews as it tests your understanding of tree data structures and your ability to manipulate them. The problem can be solved using either a recursive or iterative approach. Your task is to provide a function that takes a binary tree as input and returns the inverted tree.

Answer

Here is how you can write a function to invert a binary tree using Python, which is a popular programming language for coding interviews. We'll use a recursive approach to solve this problem.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(root):
    # Base case: if the node is None, return None
    if root is None:
        return None
    
    # Swap the left and right children
    root.left, root.right = root.right, root.left
    
    # Recursively invert the left and right subtrees
    invertTree(root.left)
    invertTree(root.right)
    
    # Return the root of the inverted tree
    return root

Explanation:

• Base Case: If the current node is None, we return None. This handles the scenario when we reach the leaves of the tree.
• Swap Operation: For each node, we swap its left and right children.
• Recursive Calls: We recursively call invertTree on the left and right children of the current node.
• Result: The function returns the root of the modified tree, which is now inverted.

This recursive approach is efficient and easy to understand, making it an excellent choice for this problem.