การค้นหาค่าต่ำสุดและสูงสุดใน Binary Search Tree ด้วย JavaScript

ใน Binary Search Tree หากดู property ว่า left child จะมีค่าน้อยกว่า parent เสมอ เราจะพบว่าถ้าเราวนไปทาง left child จนถึง node ที่ไม่มี left child เราจะเจอ element ที่เล็กที่สุดใน BST

มานำฟังก์ชันนี้ไปใช้งานกัน ตั้งแต่ตอนนี้เราจะนำฟังก์ชันเวอร์ชันเดียวไปใช้ คือ iterative หรือ recursive ในกรณีนี้เราจะสร้าง iterative function:

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

getMinVal() {
  if (this.root === null) {
    throw "Empty tree!";
  }
  let currNode = this.root;
  while (currNode.left !== null) {
    currNode = currNode.left;
  }
  return currNode.data;
}

ทดสอบการทำงานได้ดังนี้:

ตัวอย่างการใช้งาน

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
console.log(BST.getMinVal());

ผลลัพธ์

จะได้ผลลัพธ์ดังนี้:

3

เช่นเดียวกัน คุณสามารถขยายโค้ดนี้เพื่อเขียนฟังก์ชัน getMaxVal() ที่คืนค่าสูงสุดโดยวนไปทาง rightmost child เราจะใส่โค้ดไว้ให้ตรวจสอบ:

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

getMaxVal() {
  if (this.root === null) {
    throw "Empty tree!";
  }
  let currNode = this.root;
  while (currNode.right !== null) {
    currNode = currNode.right;
  }
  return currNode.data;
}