Pythonで二分探索木の最小共通祖先（LCA）を求める方法【再帰アルゴリズム解説】

最小共通祖先（LCA）とは

二分探索木（Binary Search Tree）が与えられたとき、指定された2つのノードの最小共通祖先（Lowest Common Ancestor：LCA）を求める問題を考えてみましょう。

ノード p と q の LCA とは、「p と q の両方を子孫として持つノードの中で、最も深い位置にあるノード」のことです。

例えば、次のような二分木があるとします。

[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]

この木は以下のような構造になります。

この場合、2 と 8 の LCA は 6 となります。6 は 2 と 8 の両方を子孫に持ち、それより深い共通の祖先は存在しないためです。

解法のアプローチ

この問題は再帰を使うことでシンプルに解くことができます。手順は以下の通りです。

• 木が空（null）の場合は、None を返します。
• p または q のどちらかが現在のルートと一致する場合は、そのルートを返します。
• left := ルートの左部分木に対して p と q の LCA を再帰的に求めます。
• right := ルートの右部分木に対して p と q の LCA を再帰的に求めます。
• left と right が両方とも非 null であれば、p と q が左右に分かれていることを意味するため、現在のルートが LCA となり、ルートを返します。
• それ以外の場合は、非 null になっている側（left または right）を返します。

Pythonでの実装例

それでは、実際の実装を見てみましょう。

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class Solution():
    def lowestCommonAncestor(self, root, p, q):
        if not root:
            return None
        if p == root or q == root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def search_node(root, element):
    if root == None:
        return None
    if root.data == element:
        return root
    res1 = search_node(root.left, element)
    if res1:
        return res1
    res2 = search_node(root.right, element)
    return res2

root = make_tree([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
ob1 = Solution()
op = ob1.lowestCommonAncestor(root, search_node(root, 2), search_node(root, 8))
print(op.data)

入力

[6,2,8,0,4,7,9,null,null,3,5]
2
8

出力

6

処理の流れと計算量

このアルゴリズムでは、まず目的のノード p と q を search_node 関数で探索し、そのノードオブジェクトを取得します。その後、lowestCommonAncestor メソッドが再帰的に木をたどり、p と q が左右の部分木に分かれる最初のノードを見つけ出します。

• 時間計算量： 各ノードを最大1回訪問するため、O(n) となります（n はノード数）。
• 空間計算量： 再帰呼び出しによるスタック領域として、最悪ケース（木が線形に偏っている場合）で O(n)、バランスの取れた木では O(log n) となります。

補足：BSTの性質を活用した最適化

上記のコードは一般的な二分木にも使える汎用的な手法ですが、対象が厳密な二分探索木（BST）である場合は、さらに効率よく求められます。BSTでは「左の子 ＜ 親 ＜ 右の子」という順序が保証されているため、以下のように判断できます。

• p と q が両方ともルートより小さい場合は、LCA は左部分木に存在します。
• p と q が両方ともルートより大きい場合は、LCA は右部分木に存在します。
• それ以外（p と q がルートを挟んで分かれている、あるいはどちらかがルート）の場合は、現在のルートが LCA です。

この方法では、毎回両方の部分木を探索する必要がないため、平均的により高速に LCA を特定できます。