Kata: Binary Search Tree

Table of contents

Problem Statement

Implement a binary search tree (BST) that supports:

• insert(value) — add a value maintaining BST invariant
• search(value) — check if a value exists
• delete(value) — remove a value, handling all three cases (leaf, one child, two children)
• inOrder() — return values in sorted order
• min() / max() — find minimum and maximum values

BST invariant: For every node, all values in the left subtree are less, and all values in the right subtree are greater.

Concepts

A BST provides O(log n) average-case operations, degrading to O(n) when unbalanced. Self-balancing variants (AVL, Red-Black) maintain O(log n) guarantees.

TypeScript: Uses generics with constraints for comparable values. See TypeScript Core Concepts.

Python: Uses the __lt__ dunder method for comparisons, and Python 3.12+ type parameter syntax. See Python 3.10+ Updates.

Boilerplate

TypeScript

// bst.ts
class TreeNode<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  constructor(public value: T) {}
}

class BinarySearchTree<T> {
  private root: TreeNode<T> | null = null;

  insert(value: T): void { /* TODO */ }
  search(value: T): boolean { /* TODO */ return false; }
  delete(value: T): void { /* TODO */ }
  inOrder(): T[] { /* TODO */ return []; }
  min(): T | undefined { /* TODO */ return undefined; }
  max(): T | undefined { /* TODO */ return undefined; }
}

Python

# bst.py
from __future__ import annotations

class TreeNode[T]:
    def __init__(self, value: T) -> None:
        self.value = value
        self.left: TreeNode[T] | None = None
        self.right: TreeNode[T] | None = None

class BinarySearchTree[T]:
    def __init__(self) -> None:
        self._root: TreeNode[T] | None = None

    def insert(self, value: T) -> None: ...
    def search(self, value: T) -> bool: ...
    def delete(self, value: T) -> None: ...
    def in_order(self) -> list[T]: ...
    def min(self) -> T | None: ...
    def max(self) -> T | None: ...

Hints

Solution

TypeScript

class TreeNode<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  constructor(public value: T) {}
}

class BinarySearchTree<T> {
  private root: TreeNode<T> | null = null;

  insert(value: T): void {
    this.root = this.insertNode(this.root, value);
  }

  private insertNode(node: TreeNode<T> | null, value: T): TreeNode<T> {
    if (!node) return new TreeNode(value);
    if (value < node.value) {
      node.left = this.insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.insertNode(node.right, value);
    }
    return node;
  }

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

  delete(value: T): void {
    this.root = this.deleteNode(this.root, value);
  }

  private deleteNode(
    node: TreeNode<T> | null,
    value: T
  ): TreeNode<T> | null {
    if (!node) return null;

    if (value < node.value) {
      node.left = this.deleteNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.deleteNode(node.right, value);
    } else {
      // Node found
      if (!node.left) return node.right;
      if (!node.right) return node.left;

      // Two children: find in-order successor
      let successor = node.right;
      while (successor.left) {
        successor = successor.left;
      }
      node.value = successor.value;
      node.right = this.deleteNode(node.right, successor.value);
    }
    return node;
  }

  inOrder(): T[] {
    const result: T[] = [];
    const traverse = (node: TreeNode<T> | null) => {
      if (!node) return;
      traverse(node.left);
      result.push(node.value);
      traverse(node.right);
    };
    traverse(this.root);
    return result;
  }

  min(): T | undefined {
    if (!this.root) return undefined;
    let current = this.root;
    while (current.left) current = current.left;
    return current.value;
  }

  max(): T | undefined {
    if (!this.root) return undefined;
    let current = this.root;
    while (current.right) current = current.right;
    return current.value;
  }
}

Complexity Analysis

Cross-Language Notes

PHP: PHP doesn’t have a built-in BST, but SplHeap provides a related tree-based structure for priority queues. See PHP Core Concepts. PHP’s usort() with custom comparators is the typical approach for sorted collections.

Python: Python’s bisect module provides binary search on sorted lists. For a production BST, consider the sortedcontainers library which provides SortedList, SortedDict, and SortedSet with excellent performance.

Java/C++: If you need a self-balancing BST, Java’s TreeMap (Red-Black tree) and C++‘s std::set (typically Red-Black tree) are battle-tested implementations.