二分木の最小共通祖先（LCA）

最小共通祖先（LCA）

二分木における2つのノード p と q の最小共通祖先は、p と q の両方の祖先である最も深いノードです。ノードは自身の祖先になりえます。

一般二分木での LCA

LCA(root, p, q):
  if root is NULL: return NULL
  if root == p or root == q: return root
  left  = LCA(root.left, p, q)
  right = LCA(root.right, p, q)
  if left != NULL and right != NULL: return root
  return left if left != NULL else right

BST での LCA（最適化版）

BST では順序性を活用できます：

LCA_BST(root, p, q):
  if p.value < root.value and q.value < root.value:
    return LCA_BST(root.left, p, q)   // 両方とも左部分木に
  if p.value > root.value and q.value > root.value:
    return LCA_BST(root.right, p, q)  // 両方とも右部分木に
  return root  // 分岐点 — これが LCA

この BST 版は一般二分木版の O(n) に比べ、O(h) 時間と O(h) 空間（反復的なら O(1) 空間）で実行されます。

応用

• ファイルシステム: 2つのファイルの共通親ディレクトリの検索
• バージョン管理: Git の merge-base はコミットグラフで2つのコミットの LCA を見つける
• ネットワーキング: 2つのネットワークノード間の共通ルーターの検索
• 分類法: 2つのアイテムの最も具体的な共通カテゴリの検索