Skip to main content

​
Binary Search Tree

A binary tree where each node has at most two children, and for every node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater.

​
Overview

Binary Search Trees (BST) provide O(log n) average-case performance for search, insertion, and deletion operations. The BST property enables efficient searching by eliminating half of the remaining nodes at each step.

​
Implementation

​
Node Structure

class Node<T = number> {
  leftNode: Node<T> | null = null;
  rightNode: Node<T> | null = null;
  value: T;

  constructor(value: T) {
    this.value = value;
  }
}
Reference: node.ts:1-10

​
Class Definition

class BinarySearchTree<T = number> {
  root: Node<T> | null = null;
  
  // ... methods
}
Reference: binary-search-tree.ts:3-4

​
BST Property

BST Invariant: For any node N:
  • All values in the left subtree < N.value
  • All values in the right subtree > N.value
  • Both left and right subtrees are also BSTs
       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

Left subtree of 8: {1,3,4,6,7} - all < 8
Right subtree of 8: {10,13,14} - all > 8

​
API Reference

​
insert(key: T): boolean

Inserts a new value into the tree while maintaining BST property. 
const bst = new BinarySearchTree<number>();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);
bst.insert(6);

// Tree structure:
//       8
//      / \
//     3   10
//    / \
//   1   6
Complexity:
  • Average: O(log n)
  • Worst (skewed tree): O(n)
Reference: binary-search-tree.ts:6-36

​
search(key: T): boolean

Searches for a value in the tree. 
const bst = new BinarySearchTree<number>();
bst.insert(8);
bst.insert(3);
bst.insert(10);

console.log(bst.search(3));  // true
console.log(bst.search(15)); // false
Complexity:
  • Average: O(log n)
  • Worst (skewed tree): O(n)
Reference: binary-search-tree.ts:80-98

​
min(): T | undefined

Finds the minimum value in the tree (leftmost node). 
const bst = new BinarySearchTree<number>();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);

console.log(bst.min()); // 1
Complexity: O(h) where h is the height of the tree Reference: binary-search-tree.ts:100-112

​
max(): T | undefined

Finds the maximum value in the tree (rightmost node). 
const bst = new BinarySearchTree<number>();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(14);

console.log(bst.max()); // 14
Complexity: O(h) where h is the height of the tree Reference: binary-search-tree.ts:114-126

​
remove(key: T): boolean

Removes a node from the tree while maintaining BST property. 
const bst = new BinarySearchTree<number>();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);

bst.remove(3); // true
bst.search(3); // false
Handles three cases:
  1. Leaf node: Simply remove
  2. One child: Replace with child
  3. Two children: Replace with in-order successor (minimum of right subtree)
Complexity:
  • Average: O(log n)
  • Worst (skewed tree): O(n)
Reference: binary-search-tree.ts:128-207

​
Traversal Methods

​
In-Order Traversal

Visits nodes in ascending order: left → node → right 
const bst = new BinarySearchTree<number>();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);
bst.insert(6);

const values: number[] = [];
bst.inOrderTraverse((node) => {
  values.push(node.value);
});

console.log(values); // [1, 3, 6, 8, 10]
Use case: Get sorted values Complexity: O(n) Reference: binary-search-tree.ts:38-50

​
Pre-Order Traversal

Visits nodes: node → left → right 
const values: number[] = [];
bst.preOrderTraverse((node) => {
  values.push(node.value);
});

console.log(values); // [8, 3, 1, 6, 10]
Use case: Copy tree structure, prefix expressions Complexity: O(n) Reference: binary-search-tree.ts:52-64

​
Post-Order Traversal

Visits nodes: left → right → node 
const values: number[] = [];
bst.postOrderTraverse((node) => {
  values.push(node.value);
});

console.log(values); // [1, 6, 3, 10, 8]
Use case: Delete tree, postfix expressions, calculate tree metrics Complexity: O(n) Reference: binary-search-tree.ts:66-78

​
Complexity Summary

OperationAverageWorst CaseBest Case
insertO(log n)O(n)O(1)
searchO(log n)O(n)O(1)
removeO(log n)O(n)O(1)
min/maxO(log n)O(n)O(1)
traversalO(n)O(n)O(n)
Worst case O(n) occurs when the tree becomes skewed (essentially a linked list):
Inserting in order: 1, 2, 3, 4, 5

1
 \
  2
   \
    3
     \
      4
       \
        5

Height = n, making all operations O(n)
Solution: Use a self-balancing tree

​
Common Patterns

​
Validate BST

function isValidBST<T>(
  node: Node<T> | null,
  min: T | null = null,
  max: T | null = null
): boolean {
  if (!node) return true;
  
  if ((min !== null && node.value <= min) ||
      (max !== null && node.value >= max)) {
    return false;
  }
  
  return isValidBST(node.leftNode, min, node.value) &&
         isValidBST(node.rightNode, node.value, max);
}

​
Find Closest Value

function findClosestValue(
  bst: BinarySearchTree<number>,
  target: number
): number {
  let closest = bst.root!.value;
  let current = bst.root;
  
  while (current) {
    if (Math.abs(target - closest) > Math.abs(target - current.value)) {
      closest = current.value;
    }
    
    if (target < current.value) {
      current = current.leftNode;
    } else if (target > current.value) {
      current = current.rightNode;
    } else {
      break;
    }
  }
  
  return closest;
}

​
Find Kth Smallest

function kthSmallest(bst: BinarySearchTree<number>, k: number): number {
  let count = 0;
  let result = -1;
  
  bst.inOrderTraverse((node) => {
    count++;
    if (count === k) {
      result = node.value;
    }
  });
  
  return result;
}

​
Range Query

function getValuesInRange(
  node: Node<number> | null,
  min: number,
  max: number,
  result: number[] = []
): number[] {
  if (!node) return result;
  
  // Only traverse left if we haven't passed the min
  if (node.value > min) {
    getValuesInRange(node.leftNode, min, max, result);
  }
  
  // Add current node if in range
  if (node.value >= min && node.value <= max) {
    result.push(node.value);
  }
  
  // Only traverse right if we haven't passed the max
  if (node.value < max) {
    getValuesInRange(node.rightNode, min, max, result);
  }
  
  return result;
}

​
Use Cases

BSTs are ideal for:
  • Maintaining sorted data with frequent insertions/deletions
  • Range queries (find all values between x and y)
  • Finding kth smallest/largest element
  • Auto-complete and spell checkers
  • Priority queues (when balanced)

​
Balanced vs Unbalanced

​
Balanced BST

       8
      / \
     4   12
    / \  / \
   2  6 10 14

Height: 2
Operations: O(log n)

​
Unbalanced (Skewed) BST

2
 \
  4
   \
    6
     \
      8
       \
        10

Height: 4
Operations: O(n)
For guaranteed O(log n) performance, use a self-balancing variant like AVL Tree or Red-Black Tree.

​
Key Characteristics

Advantages:
  • Average O(log n) search, insert, delete
  • Maintains sorted order
  • Efficient range queries
  • In-order traversal gives sorted sequence
  • Simple to implement
Disadvantages:
  • Can degrade to O(n) when unbalanced
  • No guaranteed balance
  • More complex than arrays for simple operations
  • Recursive operations use stack space

AVL Tree

Self-balancing BST with guaranteed O(log n)

Binary Heap

Different ordering for priority queues

Tree

General tree without ordering constraint

Build docs developers (and LLMs) love

Get started for freeTalk to us