Binary Search Trees

Binary Search Tree (BST)

A BST is a binary tree where for each node: left subtree values < node value < right subtree values. This property enables O(log n) search in balanced trees.

BST Operations

class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

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

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

  findMin() {
    let current = this.root;
    while (current && current.left) current = current.left;
    return current ? current.value : null;
  }

  findMax() {
    let current = this.root;
    while (current && current.right) current = current.right;
    return current ? current.value : null;
  }
}