C#の再帰を使って二分木が有効な二分探索木（BST）かどうかを判定する方法

二分探索木（Binary Search Tree：BST）とは、すべての左の子ノードが親ノードの値より小さく、すべての右の子ノードが親ノードの値より大きくなるという性質を満たす二分木のことです。この記事では、C#の再帰処理を利用して、与えられた二分木が有効な二分探索木であるかどうかを判定する方法を解説します。

判定アルゴリズムの考え方

判定は以下の手順で行います。

まず、ノードに値が存在するかどうかを確認します。ノードがnullの場合は空の木も有効な二分探索木とみなせるため、trueを返します。

次に、ノード・最小値・最大値を引数として渡し、再帰メソッドisValidBSTを呼び出します。各ノードには「取りうる値の範囲」をminとmaxで制約として持たせるのがポイントです。現在のノードの値がmin以下、またはmax以上であれば、その木は二分探索木の条件を満たしていないためfalseを返します。

条件を満たしている場合は、左の子ノードには「min〜現在の値」、右の子ノードには「現在の値〜max」という範囲を渡しながらisValidBSTを再帰的に呼び出します。これにより、すべてのノードが検証されるまで処理が繰り返されます。

C#での実装例

public class TreesPgm{
    public class Node{
        public int Value;
        public Node LeftChild;
        public Node RightChild;
        public Node(int value){
            this.Value = value;
        }
        public override String ToString(){
            return "Node=" + Value;
        }
    }
    public bool isValidBST(Node root){
        if (root == null){
            return true;
        }
        return isValidBST(root, int.MinValue, int.MaxValue);
    }
    private bool isValidBST(Node root, int min, int max){
        if (root == null){
            return true;
        }
        if (root.Value <= min || root.Value >= max){
            return false;
        }
        return isValidBST(root.LeftChild, min, root.Value) && isValidBST(root.RightChild,
        root.Value, max);
    }
}

入力例

    5
  2 6
1  3

出力結果

True

上記の例では、各ノードが「左の子 ＜ 親 ＜ 右の子」という条件を満たしているため、プログラムはTrueを出力します。min／maxによる範囲制約を再帰的に伝播させることで、単に隣接する親子関係だけでなく、木全体の整合性を効率よく検証できる点がこの手法の特徴です。