JavaScriptでBST（二分探索木）の左側の葉ノードの合計を求める方法

問題概要

JavaScriptで、二分探索木（BST）のルートノードを唯一の引数として受け取り、左側の葉ノードに格納されたデータの合計を計算する関数を作成する必要があります。

ここでいう「左側の葉」とは、親ノードの左の子であり、かつ左右どちらの子も持たないノードのことを指します。

具体例

たとえば、次のような木構造を考えてみましょう。

8
/ \
1 10
/ \
5 17

この場合の出力は次のようになります。

const output = 6;

出力の解説

この木には値が 1 と 5 の2つの左側の葉ノードが存在するため、それらの合計である 6 が結果となります。

実装コード

まず Node クラスと BinarySearchTree クラスを定義して挿入メソッドを実装し、その後、木を再帰的に走査して左側の葉の値だけを合計する関数を作成します。

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(3);
BST.insert(6);
BST.insert(6);
BST.insert(9);
BST.insert(4);
BST.insert(7);
const isLeaf = node => {
    if (!node) return false;
    return (node.left === null && node.right === null);
}
const traverseTreeAndSumLeftLeaves = (root, sum = 0) => {
    if (!root) return sum;
    if (isLeaf(root)) return sum;
    if (root.left) {
        if (isLeaf(root.left)) {
            sum += root.left.data;
            traverseTreeAndSumLeftLeaves(root.left, sum);
        } else sum = traverseTreeAndSumLeftLeaves(root.left, sum);
    }
    if (root.right) {
        if (isLeaf(root.right)) return sum;
        else {
            sum = traverseTreeAndSumLeftLeaves(root.right, sum);
        }
    }
    return sum;
};
console.log(traverseTreeAndSumLeftLeaves(BST.root));

コードのポイント

• isLeaf関数：渡されたノードが「葉」（左右どちらの子も持たないノード）かどうかを判定します。
• traverseTreeAndSumLeftLeaves関数：木を深さ優先で再帰的に走査し、現在のノードの左の子が葉であれば、その値を合計に加算します。
• 右側の葉は対象外：右の子が葉の場合は値を加算せず、走査のみ続行します。

出力結果

コンソールには次のように表示されます。

7

なぜ7になるのか？

このコード例では 5, 3, 6, 6, 9, 4, 7 の順で値を挿入しています。この構成では、左側の葉ノードは値 7（ノード9の左の子）の1つだけとなるため、合計は 7 になります。