1. Hash Set

Intuition

Since each node has a parent pointer, we can trace the path from p to the root and store all visited nodes in a set. Then we trace from q upward until we find a node that already exists in the set. This intersection point is the lowest common ancestor.

Algorithm

1. Create a hash set to store ancestors.
2. Traverse from p to the root, adding each node to the set.
3. Traverse from q to the root, checking if each node exists in the set.
4. Return the first node found in the set (the LCA).

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        seen = set()
        while p:
            seen.add(p)
            p = p.parent

        while q:
            if q in seen:
                return q
            q = q.parent

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

2. Iteration - I

Intuition

If we know the depth of both nodes, we can align them first. We move the deeper node upward until both nodes are at the same depth. Then we move both nodes upward in lockstep until they meet. The meeting point is the LCA. This avoids using extra space for a hash set.

Algorithm

1. Compute the height (distance to root) of both p and q.
2. If one node is deeper, move it upward until both are at the same level.
3. Move both pointers upward together until they point to the same node.
4. Return that node as the LCA.

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        def height(node):
            h = 0
            while node:
                h += 1
                node = node.parent
            return h

        h1, h2 = height(p), height(q)
        if h2 < h1:
            p, q = q, p

        diff = abs(h1 - h2)
        while diff:
            q = q.parent
            diff -= 1

        while p != q:
            p = p.parent
            q = q.parent

        return p

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

---

3. Iteration - II

Intuition

This approach is similar to finding the intersection of two linked lists. We use two pointers starting at p and q. When a pointer reaches the root (null), we redirect it to the other starting node. After at most two passes, both pointers will have traveled the same total distance and will meet at the LCA.

Algorithm

1. Initialize two pointers ptr1 = p and ptr2 = q.
2. While ptr1 != ptr2:
   • Move ptr1 to its parent, or to q if it reaches null.
   • Move ptr2 to its parent, or to p if it reaches null.
3. Return ptr1 (or ptr2) as the LCA.

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

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

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

---

Common Pitfalls

Forgetting to Handle Equal Depths

When using the height-based iteration approach, a common mistake is assuming p and q are always at different depths. If both nodes are at the same level, no adjustment is needed before the lockstep traversal. Failing to handle this case correctly can lead to infinite loops or null pointer exceptions.

Using Value Comparison Instead of Reference Comparison

Since nodes can have duplicate values, comparing p.val == q.val is incorrect. You must compare node references (p == q or p is q) to determine when the two pointers have met at the same node. Using value comparison will produce wrong results when different nodes have the same value.

Not Recognizing the Linked List Intersection Pattern

This problem is essentially finding the intersection of two linked lists (the paths from p and q to the root). The elegant two-pointer solution works because both pointers travel the same total distance before meeting. Missing this insight leads to more complex solutions using extra space for hash sets when O(1) space is achievable.