Prerequisites
Before attempting this problem, you should be comfortable with:
- Binary Trees - Understanding tree node structure with parent pointers and traversal concepts
- Hash Sets - Using sets for O(1) lookup to track visited nodes
- Two Pointers - The technique of using two pointers that traverse at different rates or from different starting points (similar to finding intersection of linked lists)
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
- Create a hash set to store ancestors.
- Traverse from
pto the root, adding each node to the set. - Traverse from
qto the root, checking if each node exists in the set. - 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.parentTime & Space Complexity
- Time complexity:
- Space complexity:
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
- Compute the height (distance to root) of both
pandq. - If one node is deeper, move it upward until both are at the same level.
- Move both pointers upward together until they point to the same node.
- 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 pTime & Space Complexity
- Time complexity:
- Space complexity:
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
- Initialize two pointers
ptr1 = pandptr2 = q. - While
ptr1 != ptr2:- Move
ptr1to its parent, or toqif it reachesnull. - Move
ptr2to its parent, or topif it reachesnull.
- Move
- Return
ptr1(orptr2) 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 ptr1Time & Space Complexity
- Time complexity:
- Space complexity:
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.