How to Invert a Binary Tree in O(n) Time: Algorithm, Proof, and Complexity Analysis

Inverting a Binary Tree in O(n) Time: Algorithm, Proof, and Complexity Analysis

This article presents an efficient algorithm to invert a binary tree in O(n) time, where 'n' is the number of nodes in the tree. We'll cover the algorithm in detail, provide pseudo-code for implementation, prove its correctness, and analyze its complexity.

Problem Statement: Given a binary tree T, design an algorithm to invert it. Inverting a binary tree means swapping the left and right children of every node.

Algorithm:

1. Start at the root of the binary tree.
2. Base Case: If the root is null, return null as there's no tree to invert.
3. Swap the left and right child of the root.
4. Recursively invert the left and right subtrees.

Pseudo-code:

function invertBinaryTree(root):
    if root is null:
        return null
    else:
        # Swap left and right children
        temp = root.left
        root.left = root.right
        root.right = temp
        
        # Recursively invert left and right subtrees
        invertBinaryTree(root.left)
        invertBinaryTree(root.right)
    return root

Correctness Proof:

We can prove the correctness of this algorithm using induction:

• Base Case: For an empty tree (root is null), the algorithm correctly returns null.
• Inductive Step: Assuming the algorithm correctly inverts the left and right subtrees, swapping the left and right children of the current node effectively inverts the current node as well. Therefore, the algorithm correctly inverts the entire binary tree.

Complexity Analysis:

• Time Complexity: O(n) - The algorithm visits each node exactly once.
• Space Complexity: O(h) - Due to recursive calls, the space complexity is proportional to the height of the tree. In the worst case (a skewed tree), h can be equal to n. However, for a balanced tree, the space complexity is O(log n).

Conclusion:

The algorithm presented here provides an efficient and intuitive way to invert a binary tree in linear time. The recursive nature of the algorithm simplifies implementation and the correctness proof. Understanding this algorithm is fundamental for mastering tree manipulation techniques in computer science.