prep4place
Back to Visualizer

Binary Search Tree (BST)

A Binary Search Tree maintains the property that left children are smaller and right children are larger than the parent node.

O(log n) averageO(n) worst case
Speed:
🌳

Tree is empty. Insert a value or generate a sample tree.

Node
Current
Path
Found
Inserted

BST Property

  1. 1Start at the root node
  2. 2Compare target value with current node
  3. 3If target < current, go to left subtree
  4. 4If target > current, go to right subtree
  5. 5Repeat until found or reach null
  6. 6BST property: left < parent < right

Complexity

Search (avg)O(log n)
Search (worst)O(n)
InsertO(log n)
SpaceO(n)

Code

class BST {
  insert(value) {
    const node = { value, left: null, right: null };
    if (!this.root) {
      this.root = node;
      return;
    }
    
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = node;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = node;
          break;
        }
        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;
  }
}