# Binary Search Trees
**URL:** https://thecodex.expert/coding/data-structures/binary-search-trees/
**Type:** data-structure | **Confidence:** high | **Verified:** 2026-06-01

## CANONICAL DEFINITION
A binary search tree (BST) is a binary tree where each node key > all keys in its left subtree and < all in its right subtree — O(log n) average search, insert, delete; O(n) in-order traversal yields sorted output.

## COMPLEXITY
- search_avg: O(log n)
- search_worst: O(n)
- insert_avg: O(log n)
- delete_avg: O(log n)
- inorder: O(n)
- space: O(n)

## REQUIRES
concepts/recursion, data-structures/linked-lists

## ENABLES
algorithms/searching/binary-search

## SOURCES
- CLRS 4th ed. Ch.12 & Ch.13
- Adelson-Velsky & Landis 1962
- Guibas & Sedgewick 1978 FOCS
- Knuth TAOCP Vol.3 §6.2.3

*The Codex Coding — thecodex.expert/coding/ — Free forever*