Can you explain what a binary search tree data structure is and how it works?

Binary Search Tree (BST) is a data structure in the form of a tree where each node contains a key, and the following condition holds for each node:

• All keys in the left subtree are less than the node's key.
• All keys in the right subtree are greater than the node's key.

This allows efficient operations such as search, insertion, and deletion with an average complexity of O(log n), provided the tree is balanced.

Example of insertion and search in BST using JavaScript:

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(key) {
    const newNode = new Node(key);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (key < current.key) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }

  search(key) {
    let current = this.root;
    while (current) {
      if (key === current.key) return true;
      current = key < current.key ? current.left : current.right;
    }
    return false;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
console.log(tree.search(5)); // true
console.log(tree.search(20)); // false