การตรวจสอบว่าค่าอยู่ใน Binary Search Tree หรือไม่ใน JavaScript

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript บน prototype object ของ BinarySearchTree ที่รับค่าเข้ามาและตรวจสอบว่าค่านั้นอยู่ใน BST หรือไม่

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

// class สำหรับ Node เดียวของ BST
class Node {
  constructor(value) {
    this.value = value;
  }
}
// class สำหรับ BST
// มีฟังก์ชัน insert node และ search node
class BinarySearchTree {
  constructor() {
    this._root = null;
  };
  insert(value) {
    let node = this, side = '_root';
    while (node[side]) {
      node = node[side];
      if (value === node.value) {
        return;
      };
      side = value < node.value ? 'left' : 'right';
    };
    node[side] = new Node(value);
  };
  contains(value) {
    let current = this._root;
    while (current) {
      if (value === current.value) {
        return true;
      };
      current = value < current.value ? current.left : current.right;
    }
    return false;
  };
}
const tree = new BinarySearchTree();
for (let i = 0; i < 10; i++) {
  tree.insert(Math.floor(Math.random() * 1000));
};
tree.insert(34);
console.log(tree.contains(34));
console.log(tree.contains(334));

ผลลัพธ์

ผลลัพธ์ที่แสดงในคอนโซลจะเป็นดังนี้:

true false