Solution Explanation for Lowest Common Ancestor of a Binary Tree III

This problem asks to find the Lowest Common Ancestor (LCA) of two nodes, p and q, in a binary tree where each node has a pointer to its parent. Two approaches are efficient: using a hash table and using two pointers.

Approach 1: Hash Table

This approach leverages the parent pointers to efficiently find the LCA.

1. Path Traversal and Storage: We traverse upwards from node p to the root, storing each visited node in a hash set (vis). This set represents the path from p to the root.

2. Second Traversal and LCA Identification: We then traverse upwards from node q to the root. For each node visited during this traversal, we check if it's present in vis. The first node encountered that is also in vis is the LCA. This is because the LCA is the lowest node that is an ancestor of both p and q.

Code (Python):

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        vis = set()
        node = p
        while node:
            vis.add(node)
            node = node.parent
        node = q
        while node not in vis:
            node = node.parent
        return node

Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we traverse almost the entire tree (if p and q are very far apart).

Space Complexity: O(N) in the worst case, as the hash set might store nearly all nodes in a skewed tree.

Approach 2: Two Pointers

This approach is even more efficient in terms of space complexity.

1. Initialization: Two pointers, a and b, are initialized to p and q, respectively.

2. Iterative Ascent: The pointers ascend towards the root simultaneously. If a pointer reaches the root (node.parent == None), it's redirected to the other node (q or p).

3. LCA Detection: The algorithm continues until a and b meet. At this point, the pointers converge at the LCA.

Code (Python):

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        a, b = p, q
        while a != b:
            a = a.parent if a.parent else q
            b = b.parent if b.parent else p
        return a
 

Time Complexity: O(N) in the worst case, similar to the hash table approach.

Space Complexity: O(1), as it uses only a constant amount of extra space.

Comparison: Both approaches have the same time complexity, but the two-pointer approach is superior in terms of space complexity. The two-pointer approach is generally preferred because of its space efficiency, especially for large trees. The hash table approach is simpler to understand but less space-efficient.