Algorithms Lesson 7: Binary Search Tree

A BST keeps data sorted: left child is always smaller, right child is always larger. This gives O(log n) search, insert, and delete in balanced trees.

BST Implementation

class BST {
  constructor() { this.root = null; }
  
  insert(val) {
    const node = new TreeNode(val);
    if (!this.root) { this.root = node; return; }
    let curr = this.root;
    while (true) {
      if (val < curr.val) {
        if (!curr.left) { curr.left = node; return; }
        curr = curr.left;
      } else {
        if (!curr.right) { curr.right = node; return; }
        curr = curr.right;
      }
    }
  }
  
  search(val) {
    let curr = this.root;
    while (curr) {
      if (val === curr.val) return true;
      curr = val < curr.val ? curr.left : curr.right;
    }
    return false;
  }
  
  // In-order gives sorted output!
  sorted() {
    const result = [];
    function inOrder(node) {
      if (!node) return;
      inOrder(node.left);
      result.push(node.val);
      inOrder(node.right);
    }
    inOrder(this.root);
    return result;
  }
}