Binary Search Tree (BST)

Definition: A node-based binary tree where the left subtree contains nodes with keys smaller than the node, and the right subtree contains nodes with keys greater, recursively, for every node in the tree.

How It Works

Every node holds a key, an optional value, and pointers to a left and right child (either of which may be null). The BST invariant, that everything in a node’s left subtree is smaller and everything in its right subtree is larger, must hold recursively at every node, not just at the root. This single property is what makes the whole tree searchable by repeated halving.

Search: start at the root; if the target equals the current node’s key, stop. If smaller, recurse/loop into the left child; if larger, into the right child. Stop when found or a null child is reached (not present).
Insertion: follow the exact same comparison path as search, and attach the new node as a leaf at the first null child encountered.
Deletion has three cases, and is the operation most implementations get wrong:
- Leaf node: remove it directly, no further work.
- One child: splice that child up into the deleted node’s position.
- Two children: find the in-order successor (the leftmost node of the right subtree, i.e. the next-larger key), copy its value into the node being deleted, then delete the successor instead, which is guaranteed to have at most one child.
Traversals: in-order (left, node, right) visits keys in ascending sorted order in O(n) time. Pre-order (node, left, right) is used for serializing/copying a tree. Post-order (left, right, node) is used for safe deletion, since children are visited before their parent is freed.

None of this requires balancing. A plain BST built from already-sorted input degenerates into a straight chain, since every new node only ever has one child, which is why production systems use a self-balancing variant (see AVL Tree and Red-Black Tree) instead of a raw BST.

Insertion, Traced Step by Step

Inserting 50, 30, 70, 20, 40, 35 into an empty BST, one node at a time:

insert(50): tree is empty -> 50 becomes the root
insert(30): 30 < 50 -> go left -> null -> attach 30 as 50's left child
insert(70): 70 > 50 -> go right -> null -> attach 70 as 50's right child
insert(20): 20 < 50 -> left to 30 -> 20 < 30 -> left -> null -> attach 20 as 30's left child
insert(40): 40 < 50 -> left to 30 -> 40 > 30 -> right -> null -> attach 40 as 30's right child
insert(35): 35 < 50 -> left to 30 -> 35 > 30 -> right to 40 -> 35 < 40 -> left -> null -> attach 35 as 40's left child

Every insertion retraces a search path and attaches at the first null it finds, so insertion cost is always exactly the depth reached, O(h), where h is the current tree height.

Complexity Analysis

Operation	Average (balanced)	Worst Case (degenerate)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
In-order traversal	O(n)	O(n)
Space	O(n)	O(n)

The average case assumes keys arrive in a reasonably random order, keeping the tree roughly balanced. There’s no structural guarantee of this; a plain BST offers none of the rebalancing logic that AVL/Red-Black trees add on top.

Why It Matters

Forms the conceptual foundation for self-balancing search trees and database indexes that need ordered range queries, not just point lookups.
Unlike a Hash Table, a BST preserves sorted order, so operations like “find all keys between X and Y” or “find the next largest key” run in O(log n + k) time (k being the result count) instead of requiring a full O(n) scan and sort.
Serves as the teaching baseline before more advanced structures (B-Trees, Red-Black Trees, Tries), because the recursive definition maps directly onto recursive algorithms, making it the standard first example of recursion applied to a non-linear structure.

Common Pitfalls

Unbalanced trees degrade performance from logarithmic O(log n) to linear O(n); inserting already-sorted data into a naive BST is the classic worst case, silently turning every operation into a linked-list traversal.
Implementing the two-children deletion case incorrectly, e.g. forgetting to also delete the successor node from its original position after copying its value, creates duplicate keys or a corrupted tree.
Assuming “BST” implies O(log n) without checking whether the specific implementation self-balances; the term BST alone guarantees nothing about height.
Comparing keys with reference equality (== on objects) instead of a proper value comparator when using custom key types, causing search to fail to find keys that are logically present.
Forgetting that an in-order traversal of an invalid (invariant-violating) tree can still look sorted locally while being globally wrong; validating BST correctness requires tracking a valid (min, max) range at each node, not just comparing to immediate children.

Comparison

	BST (unbalanced)	AVL/Red-Black Tree	Hash Table	Sorted Array
Search	O(log n) avg, O(n) worst	O(log n) guaranteed	O(1) avg	O(log n)
Insert/Delete	O(log n) avg, O(n) worst	O(log n) guaranteed	O(1) avg	O(n) (shifting)
Maintains sorted order	Yes	Yes	No	Yes
Range queries	O(log n + k)	O(log n + k)	Not supported	O(log n + k)
Memory per element	2 pointers	2 pointers + balance metadata	Hash overhead + buckets	None beyond the element
Handles frequent inserts well	Only if input order is random	Yes	Yes	No, O(n) shifting

Variants

B-Tree / B+ Tree: generalizes the BST to multi-way branching (dozens to hundreds of children per node) so that each node fits in a single disk page, minimizing the number of disk reads for a lookup. B+ Trees additionally chain all leaf nodes together, making range scans a simple linked-list walk instead of a tree traversal. This is what nearly every disk-backed database index actually uses instead of a plain binary BST.
Treap: a BST where each node also holds a randomly assigned priority, maintained as a max-heap on priority alongside the BST ordering on keys. Random priorities keep the tree balanced in expectation without any explicit rotation-triggering logic.
Splay Tree: a self-adjusting BST that moves any accessed node to the root via rotations, giving strong amortized performance for skewed, repeat-heavy access patterns (like a cache) at the cost of no strict per-operation worst-case bound.

Rough disk-read comparison for 1 billion keys:

Binary BST (branching factor 2):   height ≈ log2(1e9)   ≈ 30 -> up to 30 disk reads per lookup
B-Tree (branching factor 100):     height ≈ log100(1e9) ≈  5 -> up to 5 disk reads per lookup

Real-World Systems

Database index structures conceptually descend from the BST idea, though production databases almost always use B-Trees or B+ Trees rather than plain binary BSTs, specifically to reduce disk I/O. See AVL Tree and Red-Black Tree for the in-memory self-balancing variants that most language standard libraries use instead.
Compiler symbol tables and expression parsers sometimes use BSTs (or tries) to look up identifiers while preserving useful ordering properties for later stages like sorted diagnostics output.
File system directory structures in some implementations (e.g. certain B-Tree-based filesystems like btrfs, whose name literally comes from “B-tree file system”) use tree structures directly descended from the BST family to index file metadata.

Example

Using a BST to keep a dynamic dataset sorted while allowing fast lookups. Inserting 50, 30, 70, 20, 40 builds a tree rooted at 50 with 30 and 70 as children, and 20/40 as children of 30. Searching for 40 compares against 50 (go left), then 30 (go right), then finds 40 in 3 hops instead of scanning all 5 elements linearly. An in-order traversal of this tree yields 20, 30, 40, 50, 70, the fully sorted sequence, for free as a side effect of the tree’s shape.

Deleting 30 (a two-children case) finds its in-order successor, 40 (the leftmost node of 30’s right subtree), copies 40’s value into 30’s position, then removes the now-duplicate leaf 40.

Other Operations

Find min/max: walk left (or right) children until reaching a null pointer, O(h) where h is tree height, so O(log n) balanced or O(n) degenerate.
Successor/predecessor of a node: if the node has a right subtree, the successor is that subtree’s leftmost node; otherwise it’s the nearest ancestor for which the node lies in the left subtree, found by walking up parent pointers.
Validate BST: recursively check each node against a valid (min, max) range inherited from its ancestors, not just against its immediate children, since a node could locally look fine while still violating the invariant with a grandparent.
k-th smallest element: an in-order traversal that stops after k nodes, or, with each node augmented to store its subtree size, an O(log n) walk that uses subtree sizes to decide whether to descend left or right.

FAQ

Does a BST need to be balanced to be called a BST? No. “Binary Search Tree” only describes the ordering invariant, not any balance guarantee. AVL and Red-Black trees are BSTs with an added self-balancing property; a plain BST has neither.

What happens with duplicate keys? Implementations vary: some disallow duplicates entirely, some consistently push duplicates to the right subtree, and some store a count/list at the node instead of creating a second node. Mixing conventions within one codebase is a common source of subtle bugs.

Why is deletion harder than insertion? Insertion always adds a new leaf, a purely additive change. Deletion can remove an internal node with two children, which requires restructuring around it (the successor swap) rather than just detaching a pointer.

Referenced by

Dig deeper

Spot an error in this note?