GAZAR

Algorithm

Binary Search Trees (BSTs) Algorithm

A sorted array gives you fast search but slow inserts. A linked list gives you fast inserts but slow search. A Binary Search Tree tries to give you both.

20 Mar 2024

Binary Search Trees (BSTs) Algorithm

A sorted array gives you fast search but slow inserts. A linked list gives you fast inserts but slow search. A Binary Search Tree tries to give you both.

What It Does

A BST is a tree where every node follows one rule: left children are smaller, right children are larger. This structure lets you search, insert, and delete in O(log n) time — on average.

The Implementation

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

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

  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) { this.root = node; return; }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) { current.left = node; return; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; return; }
        current = current.right;
      }
    }
  }

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

  inorder(node = this.root, result = []) {
    if (!node) return result;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
    return result;
  }
}

const tree = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(v => tree.insert(v));

console.log(tree.search(6));     // TreeNode { value: 6, ... }
console.log(tree.inorder());     // [1, 3, 4, 6, 7, 8, 10, 13, 14]

Traversals

  • Inorder (left → node → right): gives sorted output.
  • Preorder (node → left → right): useful for copying the tree.
  • Postorder (left → right → node): useful for deleting the tree.

Complexity

OperationAverageWorst
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)

The Trap

That O(n) worst case is real. Insert sorted data into a BST — 1, 2, 3, 4, 5 — and you get a linked list. Every operation becomes linear.

Self-balancing trees (AVL, Red-Black) fix this by rebalancing after insertions and deletions. They guarantee O(log n) worst case, at the cost of more complex insert/delete logic.

The Trade-off

BSTs give you sorted order + fast operations. But if you only need fast lookup by key, a hash map is O(1) average. If you need sorted data but don't need frequent inserts, a sorted array with binary search is simpler. BSTs shine when you need both dynamic inserts and sorted traversal.

Go further
Live cohort on Maven

AI Transformation for Organisational Leaders

For directors, heads of function and founders: eight live evening sessions with Ehsan Gazar and Anoosh Zeighami, ending with a one-page 2027 AI plan for your organisation, built on a real workflow and ready for your leadership team.

$1,495, or $1,045 with code EARLYBIRD until 23 Oct.

View the live cohort
Free lessonFor Leaders: How Can AI Solve a Millennium Problem Yet Fail?Wed, 21 Oct · 7:00pm LondonSave my seat1:1Interview prep with someone who runs the loopSee how it works

Keep reading