JavaScriptで二分探索木が一値（Univalued）かどうかを判定する方法

一値二分探索木（Univalued Binary Search Tree）とは？

一値二分探索木（Univalued Binary Search Tree）とは、木を構成するすべてのノードが同じ値を持つ二分探索木（BST：Binary Search Tree）のことです。全ノードの値が完全に一致していれば「一値」とみなされ、ひとつでも異なる値が混ざっていれば「一値ではない」と判断されます。

問題の概要

今回求められているのは、二分探索木のルートノードを引数として受け取り、その木が一値である場合にのみ true を返し、そうでなければ false を返すJavaScript関数を作成することです。

たとえば、次のような値を持つノードで構成された木があるとします。

const input = [5, 5, 5, 3, 5, 6];

この配列には 5 以外に 3 と 6 という異なる値が含まれているため、期待される出力は次のようになります。

const output = false;

実装例

まずはNodeクラスとBinarySearchTreeクラスを定義してテスト用の木を構築し、そのうえで一値判定を行うisUnivalued関数を実装します。

class Node{
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    };
};
class BinarySearchTree{
    constructor(){
        // 二分探索木のルート
        this.root = null;
    }
    insert(data){
        var newNode = new Node(data);
        if(this.root === null){
            this.root = newNode;
        }else{
            this.insertNode(this.root, newNode);
        };
    };
    insertNode(node, newNode){
        if(newNode.data < node.data){
            if(node.left === null){
                node.left = newNode;
            }else{
                this.insertNode(node.left, newNode);
            };
        } else {
            if(node.right === null){
                node.right = newNode;
            }else{
                this.insertNode(node.right,newNode);
            };
        };
    };
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(5);
BST.insert(5);
BST.insert(3);
BST.insert(5);
BST.insert(6);
const isUnivalued = (root) => {
    const helper = (node, prev) => {
        if (!node) {
            return true
        }
        if (node.data !== prev) {
            return false
        }
        let isLeftValid = true
        let isRightValid = true
        if (node.left) {
            isLeftValid = helper(node.left, prev)
        }
        if (isLeftValid && node.right) {
            isRightValid = helper(node.right, prev)
        }
        return isLeftValid && isRightValid
    }
    if (!root) {
        return true
    }
    return helper(root, root.data)
};
console.log(isUnivalued(BST.root));

アルゴリズムのポイント

この実装の核となるのは、再帰的に呼び出されるhelper関数です。処理の流れは以下の通りです。

• ベースケース： ノードが存在しない場合は true を返します（空の部分木は一値とみなせるため）。
• 値の比較： 現在のノードの値が基準値（ルートの値）と一致しない場合、即座に false を返して探索を打ち切ります。
• 再帰的な探索： 左右の子ノードに対して同じチェックを再帰的に適用し、左右どちらも有効である場合のみ true を返します。

さらに、左側のチェックで false が確定した時点で右側の探索をスキップする構造になっているため、無駄な計算を抑えられるのもこの実装の利点です。

出力結果

コンソールに出力される結果は次の通りです。

false