Inverting a Binary Tree

Inverting a Binary Tree

This solution herein is expected to solve the problem of inverting a binary tree.

In other words, it aims to transform a binary tree such that for every node, its left child becomes its right child, and its right child becomes its left child.

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        """
        Initialize a TreeNode with a value and optional left and right children.

        Args:
            value (int, optional): The value of the node. Defaults to 0.
            left (TreeNode, optional): The left child of the node. Defaults to None.
            right (TreeNode, optional): The right child of the node. Defaults to None.
        """
        self.value = value
        self.left = left
        self.right = right

# O(n) time | O(n) space
def invert_binary_tree(tree):
    """
    Invert a binary tree by swapping the left and right children of each node.

    Args:
        tree (TreeNode): The root of the binary tree to be inverted.

    Returns:
        None: The binary tree is modified in-place.
    """
    # Initialize a queue for level-order traversal
    queue = [tree]

    # Perform level-order traversal (BFS)
    while len(queue) > 0:
        # Dequeue the current node
        current = queue.pop(0)
        
        # Skip if the current node is None
        if current is None:
            continue
        
        # Swap the left and right children of the current node
        swap_left_and_right(current)
        
        # Enqueue the left and right children for further processing
        queue.append(current.left)
        queue.append(current.right)


def swap_left_and_right(tree):
    """
    Swap the left and right children of a binary tree node.

    Args:
        tree (TreeNode): The node whose left and right children are to be swapped.

    Returns:
        None: The left and right children are swapped in-place.
    """
    # Swap the left and right children by reassigning their references
    tree.left, tree.right = tree.right, tree.left


# Example usage:
# Construct a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Invert the binary tree
invert_binary_tree(root)

# Output the inverted binary tree (not shown for brevity)

Let’s break it down:

The invert_binary_tree function takes a binary tree as input and inverts it by swapping the left and right subtrees at each level. It uses a queue-based approach for level-order traversal:

The swap_left_and_right function simply swaps the left and right children of a given node  by simply reassigning their references

By performing a level-order traversal and swapping the left and right children of each node, the solution effectively inverts the entire binary tree.

Time Complexity

Since every node in the binary tree is visited exactly once, the time complexity of the solution is O(n), where n is the number of nodes in the binary tree.

Space Complexity

The solution uses a queue to perform level-order traversal. At any point in time, the queue may contain nodes at most equal to the maximum number of nodes at any level in the binary tree.

In the worst case, when the binary tree is fully balanced, the number of nodes at the last level is approximately n/2. Therefore, the space complexity due to the queue is O(n).

Alternative implementation

Here's an alternative approach to the implementation above,

# O(n) time | O(d) space	
def invert_binary_tree(tree):
    """
    Inverts a binary tree by swapping the left and right children of each node.

    Args:
        tree (TreeNode): The root of the binary tree.

    Returns:
        None: The tree is modified in-place.
    """
    if tree is None:
        return

    # Swap left and right children
    swap_left_and_right(tree)

    # Recursively invert left and right subtrees
    invert_binary_tree(tree.left)
    invert_binary_tree(tree.right)

def swap_left_and_right(tree):
    """
    Swaps the left and right children of a given node.

    Args:
        tree (TreeNode): The node whose children need to be swapped.
    """
    tree.left, tree.right = tree.right, tree.left