Tìm giá trị nhỏ nhất và lớn nhất trong Binary Search Tree JavaScript

Trong Binary Search Tree, nếu nhìn vào đặc tính rằng con bên trái luôn nhỏ hơn cha, ta sẽ thấy rằng nếu cứ lặp về phía con trái cho đến khi gặp nút không có con trái, ta sẽ tìm thấy phần tử nhỏ nhất trong BST.

Hãy triển khai hàm này trong code. Từ nay chúng ta sẽ chỉ triển khai phiên bản đơn lẻ của hàm, tức là hoặc lặp hoặc đệ quy. Trong trường hợp này, ta sẽ tạo hàm lặp:

Ví dụ

getMinVal() {
  if (this.root === null) {
    throw "Cây rỗng!";
  }
  let currNode = this.root;
  while (currNode.left !== null) {
    currNode = currNode.left;
  }
  return currNode.data;
}

Bạn có thể kiểm tra bằng cách sau:

Ví dụ

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());

Kết quả

Điều này sẽ cho ra kết quả:

3

Tương tự, bạn có thể mở rộng code này để viết hàm getMaxVal() trả về giá trị lớn nhất bằng cách lặp qua các con bên phải nhất. Chúng ta chỉ đưa code ở đây để bạn xác minh:

Ví dụ

getMaxVal() {
  if (this.root === null) {
    throw "Cây rỗng!";
  }
  let currNode = this.root;
  while (currNode.right !== null) {
    currNode = currNode.right;
  }
  return currNode.data;
}