Lowest Common Ancestor of a Binary Tree III

medium tree two pointers lca

Problem

You are given two nodes p and q of a binary tree. Each node carries a parent pointer in addition to left and right. There is no separate root reference. Return their lowest common ancestor.

Walking from any node through its parents reaches the root, so each node defines a path to the root. The LCA is the first node shared by the two upward paths.

Inputtree = [3,5,1,6,2,0,8], p = 5, q = 1

Output3

Walking up from 5 reaches 3; walking up from 1 reaches 3. Their first shared ancestor is 3.

level-order (use "null" for missing children)

def lowest_common_ancestor(p, q):
    a, b = p, q
    while a is not b:
        a = a.parent if a else q
        b = b.parent if b else p
    return a

function lowestCommonAncestor(p, q) {
  let a = p, b = q;
  while (a !== b) {
    a = a ? a.parent : q;
    b = b ? b.parent : p;
  }
  return a;
}

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while (a != b) {
            a = (a != null) ? a.parent : q;
            b = (b != null) ? b.parent : p;
        }
        return a;
    }
}

Node* lowestCommonAncestor(Node* p, Node* q) {
    Node* a = p;
    Node* b = q;
    while (a != b) {
        a = a ? a->parent : q;
        b = b ? b->parent : p;
    }
    return a;
}

Explanation

This is the same trick used to find where two linked lists intersect. Each node's chain of parent pointers is a path that ends at the root, and the two paths from p and q share a tail starting at the LCA.

The obstacle is that the two paths can have different lengths, so naively stepping both up one at a time would never line them up. The fix: when a pointer runs off the top (becomes null), restart it at the other node.

By switching starting points, both pointers traverse exactly len(path_p) + len(path_q) steps before meeting. They cover the same total distance, so they arrive at the shared node at the same moment.

If they meet at a real node, that node is the LCA. (If the trees were disjoint they would both become null together — equal — and the loop ends, but with a single tree they always meet at the LCA.)

Example with p = 5, q = 1: a walks 5 → 3, b walks 1 → 3; both reach 3 after one step, so they meet at 3 → LCA = 3.

Time: O(h) Space: O(1)