JavaScriptの二分探索木の検索モード

モード：

データセットのモードは、単にそのデータセットで最も多くの回数発生する数です。たとえば、3は、データセット2、3、1、3、4、2、3、1のモードであり、ほとんどの場合に発生します。

二分探索木

ツリーDSは、次の条件を満たす場合に有効な二分探索木です-

• ノードの左側のサブツリーには、ノードのキー以下のキーを持つノードのみが含まれています。

• ノードの右側のサブツリーには、ノードのキー以上のキーを持つノードのみが含まれます。

• 左右のサブツリーもバイナリ検索ツリーである必要があります。

問題

唯一の引数としてBSTルートを受け取るJavaScript関数を作成する必要があります。 BSTには、重複が含まれている可能性があります。ツリーに保存されているデータのモードを見つけて返す必要があります。

例

このためのコードは-

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      // root of a binary seach tree
      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(3);
BST.insert(2);
BST.insert(3);
BST.insert(2);
const findMode = function(root) {
   let max = 1;
   const hash = {};
   const result = [];
   const traverse = node => {
      if (hash[node.data]) {
         hash[node.data] += 1;
         max = Math.max(max, hash[node.data]);
      } else {
         hash[node.data] = 1;
      };
      node.left && traverse(node.left);
      node.right && traverse(node.right);
   };
   if(root){
      traverse(root);
   };
   for(const key in hash) {
      hash[key] === max && result.push(key);
   };
   return +result[0];
};
console.log(findMode(BST.root));

出力

そして、コンソールの出力は-

3