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

Question Analysis

This question is asking you to demonstrate your understanding and ability to manipulate binary tree data structures in your chosen programming language. Specifically, the task is to invert a binary tree, which means swapping the left and right children of all nodes in the tree. This is a common problem that tests your knowledge of tree traversal algorithms, such as depth-first search (DFS) or breadth-first search (BFS), and your ability to implement recursive or iterative solutions. The problem is often solved using a recursive approach, which is both intuitive and concise for tree structures.

Answer

Here is how you can write a function to invert a binary tree in Python using a recursive approach:

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

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

Explanation:

• Base Case: The recursion stops when it encounters a None node, which means we've reached the end of a branch.
• Swap Operation: For each node, the left and right child nodes are swapped.
• Recursive Calls: The function calls itself recursively on the left and right children to ensure all subtrees are inverted.
• Return Value: The function returns the root of the inverted tree, which will have all of its subtrees inverted.

This solution effectively demonstrates the use of recursion to traverse and manipulate binary tree structures.