Lowest Common Ancestor of a Binary Tree III

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

"""
# 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

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node* q) {
        Node* ptr1 = p;
        Node* ptr2 = q;
        while (ptr1 != ptr2) {
            ptr1 = ptr1 ? ptr1->parent : q;
            ptr2 = ptr2 ? ptr2->parent : p;
        }
        return ptr1;
    }
};