JavaScriptで二分探索木（BST）内の最小絶対差を求める方法

問題の概要

数値データを格納した二分探索木（BST）のルートノードを受け取り、木に存在する任意の2つのノード間の絶対差の最小値を返すJavaScript関数を作成します。

例として、次のような二分探索木を考えてみましょう。

1
 \
  3
 /
2

この木に対する期待される出力は以下の通りです。

const output = 1;

これは |1 − 2| = |3 − 2| = 1 となるためです。

解法のポイント：中順走査の活用

二分探索木には「中順走査（In-order Traversal）を行うとノードの値が必ず昇順に並ぶ」という重要な性質があります。この性質を利用すれば、すべてのノードペアを総当たりで比較する必要はなく、昇順に並んだ値の隣接要素同士の差だけを調べればよいため、計算量を O(n) に抑えることができます。

実装例

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(1);
BST.insert(3);
BST.insert(2);
const getMinimumDifference = function(root) {
   const nodes = [];
   const dfs = (root) => {
      if(root) {
         dfs(root.left);
         nodes.push(root.data);
         dfs(root.right);
      };
   };
   dfs(root);
   let result = nodes[1] - nodes[0];
   for(let i = 1; i < nodes.length - 1; i++) {
      result = Math.min(result, nodes[i + 1] - nodes[i]);
   };
   return result;
};
console.log(getMinimumDifference(BST.root));

出力結果

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

1

コードの解説

まず、Node クラスで各ノードの構造（値・左の子・右の子）を定義し、BinarySearchTree クラスでノードを挿入するメソッドを実装しています。

核心となる getMinimumDifference 関数では、再帰的な DFS（深さ優先探索）による中順走査でノードの値を訪問順に配列 nodes へ格納します。中順走査によって配列は昇順にソートされた状態になるため、あとは隣接する2要素の差を順に比較し、その最小値を Math.min で更新していくだけで答えが得られます。