Binary Search Tree

BST implementation with insertion, search, and traversal operations

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

Operation	Average	Worst Case	Best Case
insert	O(log n)	O(n)	O(1)
search	O(log n)	O(n)	O(1)
remove	O(log n)	O(n)	O(1)
min/max	O(log n)	O(n)	O(1)
traversal	O(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

Related Data Structures

AVL Tree

Self-balancing BST with guaranteed O(log n)

Binary Heap

Different ordering for priority queues

Tree

General tree without ordering constraint