Youngest Common Ancestor

Tags

Youngest Common Ancestor

Category

Graphs

Difficulty

Medium

Problem Statement

Given three inputs: the top ancestor of a tree (not necessarily binary), and two descendant nodes, find the youngest (deepest, lowest) common ancestor of the two descendant nodes. Each node has a reference to its parent (an ancestor property). The youngest common ancestor is the deepest node that is an ancestor of both given nodes (a node is considered an ancestor of itself).

Intuition

If both nodes are at the same depth, we can walk both pointers up simultaneously until they meet. If they are at different depths, we first bring the deeper node up to the same depth as the shallower one, then walk both up in tandem. The node where the two pointers converge is the youngest common ancestor.

This is analogous to the "intersection of two linked lists" problem, where the lists merge at some common ancestor.

Approach

  1. Compute the depth of both descendant nodes by counting steps to the top ancestor.
  2. Determine which node is deeper and by how much.
  3. Advance the deeper node upward by the depth difference.
  4. Now both nodes are at the same depth. Walk both upward simultaneously until they point to the same node.
  5. Return that node.

Pseudocode

function getYoungestCommonAncestor(topAncestor, descendantOne, descendantTwo):
    depthOne = getDepth(descendantOne, topAncestor)
    depthTwo = getDepth(descendantTwo, topAncestor)

    if depthOne > depthTwo:
        return walkUp(descendantOne, descendantTwo, depthOne - depthTwo)
    else:
        return walkUp(descendantTwo, descendantOne, depthTwo - depthOne)

function getDepth(node, topAncestor):
    depth = 0
    while node != topAncestor:
        node = node.ancestor
        depth += 1
    return depth

function walkUp(lowerNode, higherNode, diff):
    while diff > 0:
        lowerNode = lowerNode.ancestor
        diff -= 1
    while lowerNode != higherNode:
        lowerNode = lowerNode.ancestor
        higherNode = higherNode.ancestor
    return lowerNode

Time & Space Complexity

  • Time: O(d), where d is the depth of the deeper node. We traverse up the tree at most twice.
  • Space: O(1). Only pointer variables are used.

Key Insights

  • The parent pointer makes this much simpler than LCA in a tree without parent pointers (which requires preprocessing or Euler tour techniques).
  • Equalizing depths first is the key step; without it, the two pointers would never synchronize.
  • This algorithm also works when one node is an ancestor of the other.
  • An alternative approach stores all ancestors of one node in a set, then walks up from the other node checking for membership. This uses O(d) space.

Edge Cases

  • One descendant is an ancestor of the other: the ancestor node is the youngest common ancestor.
  • Both descendants are the same node: that node itself is the answer.
  • Both descendants are direct children of the top ancestor: the top ancestor is the answer.
  • One or both descendants are the top ancestor itself.
  • Deeply unbalanced tree where one path is much longer than the other.

Linked mentions