Problem Description

You are given two nodes p and q from a binary tree where each node has a reference to its parent node. Your task is to find their lowest common ancestor (LCA).

The node structure includes:

• val: the value of the node
• left: pointer to the left child
• right: pointer to the right child
• parent: pointer to the parent node

The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants. Note that a node can be considered a descendant of itself.

The solution uses a hash table approach:

1. First, traverse from node p upward to the root, storing all visited nodes in a set vis. This captures the complete path from p to the root.

2. Then, traverse from node q upward toward the root. The first node encountered that exists in the vis set is the lowest common ancestor, since it's the first shared node on both paths to the root.

3. Return this node as the result.

The time complexity is O(h) where h is the height of the tree, as we might need to traverse from a leaf to the root in the worst case. The space complexity is also O(h) for storing the visited nodes in the hash set.

Intuition

Since each node has a parent pointer, we can think of the problem as finding where two paths converge. If we trace the path from any node to the root, we get a unique sequence of nodes. The key insight is that the paths from p to root and from q to root must eventually meet at some common node - at the very least, they'll meet at the root itself.

The lowest common ancestor is simply the first point where these two paths intersect when viewed from the bottom up. This is similar to finding the intersection point of two linked lists.

We can visualize this: imagine climbing up from node p to the root and marking every node we visit along the way. Then, if we climb up from node q, the first marked node we encounter must be the lowest common ancestor. This is because:

1. It's definitely a common ancestor (both paths pass through it)
2. It's the lowest one (it's the first common node we find when climbing up from q)

This naturally leads to the hash table solution: we record all nodes on the path from p to root in a set, then traverse from q upward until we find a node that exists in our set. This intersection point is guaranteed to be the LCA.

The elegance of this approach is that we don't need to worry about the tree structure, left/right children, or complex recursion. We simply follow parent pointers upward, turning a tree problem into a path intersection problem.

Learn more about Tree, Two Pointers and Binary Tree patterns.

Solution Approach

The implementation uses a hash table (set) to efficiently track and find the intersection of two paths. Here's how the algorithm works step by step:

Step 1: Build the path from p to root

vis = set()
node = p
while node:
    vis.add(node)
    node = node.parent

We initialize an empty set vis to store visited nodes. Starting from node p, we traverse upward by following parent pointers, adding each node to the set. This continues until we reach the root (when node becomes None).

Step 2: Find the intersection point from q

node = q
while node not in vis:
    node = node.parent
return node

Starting from node q, we traverse upward toward the root. At each step, we check if the current node exists in our vis set. The first node that exists in vis is the lowest common ancestor, and we immediately return it.

Why this works:

• The set vis contains all ancestors of p (including p itself)
• When traversing from q upward, we're guaranteed to eventually find a common node since all paths lead to the root
• The first common node we encounter is the lowest (closest to p and q) common ancestor

Time and Space Complexity:

• Time: O(h) where h is the height of the tree. In the worst case, we traverse from a leaf to the root twice.
• Space: O(h) for storing up to h nodes in the hash set when one node is deep in the tree.

The beauty of this solution is its simplicity - by leveraging the parent pointers and a hash table, we transform the tree problem into a straightforward path intersection problem.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Consider this binary tree:

        3
       / \
      5   1
     / \   \
    6   2   8
       / \
      7   4

Where each node has a parent pointer (not shown for clarity). Let's find the LCA of nodes p = 7 and q = 4.

Step 1: Build the path from p (node 7) to root

Starting from node 7, we traverse upward using parent pointers:

• Start at node 7, add to set: vis = {7}
• Move to parent (node 2), add to set: vis = {7, 2}
• Move to parent (node 5), add to set: vis = {7, 2, 5}
• Move to parent (node 3), add to set: vis = {7, 2, 5, 3}
• Move to parent (None - we've reached root), stop

Our set now contains the complete path from node 7 to the root: {7, 2, 5, 3}

Step 2: Traverse from q (node 4) upward until we find intersection

Starting from node 4, we check each node against our set:

• Start at node 4: Is 4 in vis? No, move up
• Move to parent (node 2): Is 2 in vis? Yes!

Node 2 is the first node we encounter that exists in our set, so node 2 is the LCA.

Verification: Node 2 is indeed the lowest common ancestor of nodes 7 and 4 - it's their direct parent and the lowest node that has both as descendants.

Let's try another example with p = 6 and q = 8:

Step 1: Build path from node 6 to root:

• Path: 6 → 5 → 3 → None
• vis = {6, 5, 3}

Step 2: Traverse from node 8 upward:

• Node 8: Not in vis, move up
• Node 1: Not in vis, move up
• Node 3: Found in vis!

Node 3 is the LCA of nodes 6 and 8, which makes sense as it's the root and the only node that has both as descendants.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of nodes in the binary tree. In the worst case, we need to traverse from node p to the root (up to n nodes), storing each node in the set. Then we traverse from node q upward until we find a node that exists in the set (up to n nodes in the worst case). Therefore, the total time complexity is O(n) + O(n) = O(n).

The space complexity is O(n), where n is the number of nodes in the binary tree. In the worst case, if node p is a leaf node and the root is the lowest common ancestor, we need to store all nodes from p to the root in the vis set, which could be up to n nodes in a skewed tree. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Case Where a Node is Its Own Ancestor

A common mistake is assuming that the LCA must be a strict ancestor (excluding the nodes themselves). However, by definition, a node can be a descendant of itself, meaning if p is an ancestor of q (or vice versa), then p (or q) itself is the LCA.

Incorrect Approach:

# Wrong: Starting from parent instead of the node itself
vis = set()
node = p.parent  # WRONG: Skips p itself
while node:
    vis.add(node)
    node = node.parent

Why it fails: If q is a descendant of p, this approach would miss p as the LCA and incorrectly return p's parent or a higher ancestor.

Correct Solution: Always include the starting node in the visited set:

vis = set()
node = p  # Correct: Start with p itself
while node:
    vis.add(node)
    node = node.parent

2. Infinite Loop When Parent Pointers Form a Cycle

While rare in properly constructed trees, if there's a bug in tree construction that creates a cycle in parent pointers, the traversal could get stuck in an infinite loop.

Vulnerable Code:

while node:
    vis.add(node)
    node = node.parent  # Could loop forever if there's a cycle

Defensive Solution: Add cycle detection or limit traversal depth:

vis = set()
node = p
while node and node not in vis:  # Check for cycles
    vis.add(node)
    node = node.parent

3. Not Validating Input Nodes

The code assumes both p and q are valid nodes in the same tree. If they're from different trees or if either is None, the algorithm could fail or produce incorrect results.

Problem Scenario:

• If p and q are from different trees, the second traversal might never find a common ancestor
• If either node is None, the code would crash with an AttributeError

Robust Solution: Add input validation:

def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
    if not p or not q:
        return None
  
    # Rest of the algorithm...
    visited_ancestors = set()
    current_node = p
    # ...

4. Memory Optimization Opportunity Missed

For very deep trees, storing all ancestors of p might use significant memory. An alternative two-pointer approach can achieve O(1) space complexity.

Space-Efficient Alternative:

def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
    # Get depths of both nodes
    def get_depth(node):
        depth = 0
        while node:
            depth += 1
            node = node.parent
        return depth
  
    depth_p = get_depth(p)
    depth_q = get_depth(q)
  
    # Align both nodes to same depth
    while depth_p > depth_q:
        p = p.parent
        depth_p -= 1
    while depth_q > depth_p:
        q = q.parent
        depth_q -= 1
  
    # Move both upward until they meet
    while p != q:
        p = p.parent
        q = q.parent
  
    return p

This approach uses O(1) extra space but requires two initial passes to calculate depths, maintaining the same O(h) time complexity.