Solution Explanation: Inverting a Binary Tree

The problem asks to invert a given binary tree. Inverting a binary tree means swapping the left and right children of every node in the tree.

Approach: Recursion

The most efficient and elegant way to solve this problem is using recursion. The recursive approach leverages the self-similar structure of a binary tree. Each subtree can be inverted independently, and the process can be repeated until all subtrees (including individual nodes) are inverted.

Algorithm

1. Base Case: If the current node (root) is null (empty), there's nothing to invert, so return null.

2. Recursive Step:

   • Recursively invert the left subtree (invertTree(root.left)).
   • Recursively invert the right subtree (invertTree(root.right)).
   • Swap the left and right children of the current node: root.left = right and root.right = left.
   • Return the inverted root node.

Code Implementation (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        
        left_inverted = self.invertTree(root.left)
        right_inverted = self.invertTree(root.right)
        
        root.left = right_inverted
        root.right = left_inverted
        
        return root

The code in other languages follows the same recursive structure, only differing in syntax.

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once during the recursive traversal.

• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In the best case (a balanced tree), H would be log₂(N). Therefore, the space complexity is O(N) in the worst case and O(log N) in the best case. Averaged over all possible tree shapes, the space complexity is considered O(log N) for a balanced tree and O(N) for a completely unbalanced tree.