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