Course4all
Join us on telegram
Home/dsa/Trees/Lowest Common Ancestor III

Lowest Common Ancestor III

Master this topic with zero to advance depth.

Lowest Common Ancestor III

With parent pointers.

Hard
Approach 1

Level I: Set of Ancestors

Intuition

Since each node has a parent pointer, we can trace the path from node p back to the root, storing all ancestors in a Hash Set. Then, trace back from node q. The first ancestor of q that is already in the set is the LCA.

Thought Process

  1. Traverse from p to root, adding every node to Set.
  2. Traverse from q to root.
  3. Return first node found in Set.
⏱ O(H)💾 O(H)

Detailed Dry Run

NodeSet (Ancestors of P)In Set?
P=5{5}-
3 (parent of 5){5, 3}-
Q=1{5, 3}NO
3 (parent of 1){5, 3}YES! (Result=3)
java
public class Main {
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> set = new HashSet<>();
        while (p != null) {
            set.add(p);
            p = p.parent;
        }
        while (q != null) {
            if (set.contains(q)) return q;
            q = q.parent;
        }
        return null;
    }
}
Approach 2

Level II: Depth Alignment

Intuition

We can calculate the depth of both nodes p and q. Then, move the deeper node up its parent chain until both nodes are at the same depth. From there, move both up together until they meet.

Logic

  1. Calculate depthP and depthQ.
  2. Align depths by moving up parent pointers.
  3. Move both until p == q.
⏱ O(H)💾 O(1)

Detailed Dry Run

P at depth 3, Q at depth 2. Move P up once. Both at depth 2. Move together -> meet at LCA.

java
public class Main {
    public Node lowestCommonAncestor(Node p, Node q) {
        int d1 = getD(p), d2 = getD(q);
        while (d1 > d2) { p = p.parent; d1--; }
        while (d2 > d1) { q = q.parent; d2--; }
        while (p != q) { p = p.parent; q = q.parent; }
        return p;
    }
    private int getD(Node n) {
        int d = 0; while (n != null) { n = n.parent; d++; } return d;
    }
}
Approach 3

Level III: Optimal (Two Pointers / Intersection)

Intuition

Thought Process

This problem is equivalent to finding the intersection of two linked lists. We use two pointers, a and b.

  1. Pointer a starts at p, b starts at q.
  2. When a pointer reaches the root (null), it jumps to the other starting node (q or p).
  3. They will eventually meet at the intersection point (the LCA) after at most O(H)O(H) steps.

Logic

a = (a == null) ? q : a.parent b = (b == null) ? p : b.parent

⏱ O(H)💾 O(1)

Detailed Dry Run

StepPtr APtr BNotes
151Start
233MEET! (LCA=3)
java
public class Main {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while (a != b) {
            a = (a == null) ? q : a.parent;
            b = (b == null) ? p : b.parent;
        }
        return a;
    }
}

⚠️ Common Pitfalls & Tips

Be extremely careful with the null jumping logic. If you jump at the wrong node, you might enter an infinite loop. The pointers must switch to the other starting node to align their path lengths.

← Previous QuestionSerialize and Deserialize N-ary Tree
Next Question →Path Sum IV