In a programming language you are proficient in, how would you code a binary tree inversion?

Question Analysis

The question is asking you to demonstrate your understanding and ability to manipulate binary trees, a fundamental data structure in computer science. Specifically, the task is to "invert" a binary tree, which means to swap the left and right children of all nodes in the tree. This operation is sometimes referred to as "mirroring" the tree. The question is testing your knowledge of tree data structures, recursion or iterative methods, and your proficiency in a specific programming language.

Answer

To invert a binary tree, you can use a recursive approach. Below is an implementation in Python:

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

def invert_tree(node):
    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 node

Explanation:

• Base Case: If the node is None, return None. This handles leaf nodes and empty trees.
• Swap: For each node, swap its left and right child.
• Recursive Calls: Recursively call the function on the left and right children to continue inverting the tree down the levels.
• Return: Finally, return the root node, which now represents the inverted tree.

This recursive solution is clear and leverages the natural hierarchical structure of trees. It has a time complexity of O(n), where n is the number of nodes in the tree, since each node is visited once. The space complexity is O(h), due to the recursion stack, where h is the height of the tree.