Pythonで二分木から最大の二分探索木（BST）サブツリーを見つける方法

二分木が与えられたとき、その中から「二分探索木（BST）」として成立する最大の部分木（ノード数が最大のもの）を見つける問題を考えてみましょう。

問題の概要

例えば、次のような二分木が入力として与えられた場合を想定します。

このとき、出力は以下のようになります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• max_size := [0]、max_node := [null] を初期化する
• 関数 traverse() を定義する。引数は node
• node が null の場合は null を返す
• left := traverse(node の左の子)、right := traverse(node の右の子) を再帰的に呼び出す
• lst := left + [node の値] + right を作成する
• lst がソート済み（昇順）であれば、それは BST であることを意味する
  • max_size[0] < lst のサイズ であれば、max_size[0] := lst のサイズ、max_node[0] := node を更新する
• lst を返す
• traverse(root) を実行する
• メインメソッドから max_node[0] を返す

このアルゴリズムでは、各ノードに対して左部分木と右部分木の値のリストを結合し、そのリストが昇順にソートされているかどうかで BST かどうかを判定しています。ソートされていれば、その部分木は二分探索木の条件（左の子孫 < 親 < 右の子孫）を満たしていることになります。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.val, end = ', ')
      print_tree(root.right)
class Solution:
   def solve(self, root):
      max_size = [0]
      max_node = [None]
      def traverse(node):
         if not node:
            return []
      left = traverse(node.left)
      right = traverse(node.right)
      lst = left + [node.val] + right
      if sorted(lst) == lst:
         if max_size[0] < len(lst):
            max_size[0] = len(lst)
            max_node[0] = node
      return lst

   traverse(root)
   return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))

入力

root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)

出力

4, 5, 6,

まとめ

この例では、ルートの値 12 よりも右側の部分木（5 を根とする部分木）が二分探索木の条件を満たしており、その中でも最大の BST サブツリーとして 4 → 5 → 6 が出力されています。この手法はシンプルで分かりやすい一方、各ノードでリストの生成とソート判定を行うため計算量は O(n²) 程度になります。より大きなツリーを扱う場合は、各部分木の最小値・最大値・サイズを bottom-up で伝播させる O(n) の最適化手法もあります。