Solution Explanation: Lowest Common Ancestor of a Binary Tree

This problem asks to find the lowest common ancestor (LCA) of two nodes, p and q, in a binary tree. The LCA is the lowest node in the tree that has both p and q as descendants (a node is considered a descendant of itself).

Approach: Recursive Post-order Traversal

The most efficient approach is a recursive post-order traversal of the binary tree. The core idea is as follows:

1. Base Case: If the current node (root) is null, p, or q, we return the current node. This handles the cases where we've reached the end of a branch or found one of the target nodes.

2. Recursive Calls: We recursively call the lowestCommonAncestor function on the left and right subtrees. This explores both sides of the tree to see if p and q are present in each subtree.

3. Result Combination:

   • If both recursive calls (left and right) return non-null nodes, it means p and q are found in different subtrees. Therefore, the current node (root) is their LCA, and we return it.
   • If only one of the recursive calls returns a non-null node, it implies that one of p or q is in that subtree. We return the non-null result (the node found in that subtree).
   • If both recursive calls return null, it means neither p nor q is in the current node's subtree, so we return null.

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case, we visit each node once during the traversal.
• Space Complexity: O(H), where H is the height of the binary tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, resulting in O(N) space complexity. In a balanced tree, H is log₂(N), leading to O(log₂(N)) space complexity.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, Javascript)

The code examples in various languages demonstrate the recursive approach. They all follow the same logic described above. Note the slight variations in syntax and how null (or None) is handled in different languages. The comments in the code highlight the key steps.

Example in Python:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:  # Base case
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:  # p and q are in different subtrees
            return root
        return left if left else right # return the one that is not null
 
 

The other languages' code examples follow a similar structure, adapting the syntax and null handling to their respective language conventions. The core recursive logic remains consistent across all implementations.