หา Mode (ค่าที่พบบ่อยสุด) ใน Binary Search Tree ด้วย JavaScript

Mode

ค่าที่เกิดบ่อยที่สุดในชุดข้อมูล

Binary Search Tree

BST: ซ้าย ≤ โหนด ≤ ขวา ทั้งสองฝั่งก็เป็น BST

ปัญหา

รับราก BST (อาจมีค่าซ้ำ) หา Mode ของข้อมูลในต้นไม้

โค้ดตัวอย่าง

class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; } }; 
class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ ... } insertNode(node, 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