Smaller on the left, larger on the right — one rule that turns search into a series of halvings. Then insert sorted data and watch the whole structure collapse into a linked list.
Controls
Traversal
The Tree
step 0
Insight
The BST rule, applied at every node: everything in the left subtree is smaller, everything in the right subtree is larger.
nodes0
height0
ideal height0
last search steps–
Complexity
Search (balanced)O(log n)
Search (degenerate)O(n)
SpaceO(n)
Binary Search Trees
Binary search made into a structure — and what happens when it loses its shape.
Quick Context
A binary search tree keeps its values in sorted order by position. At every node: the entire left subtree is smaller, the entire right subtree is larger. Searching then works exactly like binary search — compare, discard half, repeat.
Search, Insert, Delete
Searching is a walk: compare with the current node, go left if smaller, right if larger, stop when equal or when you fall off the tree. Insertion follows the same walk and attaches the new node where the search failed.
Deletion is the fiddly one, with three cases:
Leaf — just remove it.
One child — the child takes its place.
Two children — replace the value with its in-order successor (the smallest value in the right subtree), then delete that successor. Only this choice preserves the BST rule.
In-Order Traversal Sorts For Free
Visit left subtree, then the node, then the right subtree. Because of the BST rule, this emits every value in ascending sorted order — press In and read the output.
The other two orders have their own uses: pre-order (node first) is how you copy or serialise a tree, and post-order (node last) is how you delete one safely, since children are freed before their parent.
The Fatal Weakness
Press Sorted input. Inserting already-sorted values means every new value is larger than everything before it, so it always goes right. The tree becomes a single downward chain — a linked list wearing a tree costume.
Height goes from O(log n) to O(n), and every operation degrades with it. This is not a rare edge case: inserting sorted data is extremely common in practice.
Which Is Why Self-Balancing Trees Exist
AVL trees and red-black trees detect when a subtree grows lopsided and perform rotations to restore balance, guaranteeing O(log n) regardless of insertion order. Red-black trees are what back std::map in C++ and TreeMap in Java.
Compare the height readout after pressing Balanced versus Sorted input with the same values — the gap is exactly what balancing buys.
BST or Hash Table?
A hash table is faster for pure lookup — O(1) versus O(log n). But a BST keeps its data ordered, which a hash table cannot. Use a tree when you need sorted iteration, range queries ("all values between 20 and 50"), or nearest-neighbour lookups. Use a hash table when you only ever ask "is this exact key present?".
Interactive Exploration Guide
Insert a few values and watch each one walk down the tree, going left or right at every comparison.
Search for something. The highlighted path shows roughly half the remaining tree being discarded at each step.
Press In-order traversal. The values come out perfectly sorted — that is the BST rule paying off.
Press Sorted input. The tree collapses into a straight line and the height jumps to n — every search is now linear.
Delete a node with two children and note which value replaces it: the in-order successor, the only choice that keeps the ordering intact.
Key Takeaway
A BST turns the binary-search idea into a living structure with O(log n) search, insert and delete — but only while it stays bushy. Sorted input degenerates it to a linked list, which is precisely why self-balancing variants exist and why they, not plain BSTs, are what production libraries ship.
Cheat sheet
Binary Search Trees
Smaller on the left, larger on the right — one rule that turns search into a series of halvings. Then insert sorted data and watch the whole structure collapse into a linked list.