Binary search trees work by storing keys in a tree where every node divides the remaining search space into values that compare smaller and values that compare larger. That ordering invariant lets search follow one branch at a time instead of scanning every node.
A binary search tree is not automatically balanced. Its speed depends on height. If insertion order keeps the tree reasonably shallow, search, insertion and deletion can follow paths proportional to logarithmic height. If the tree degenerates into a long chain, those operations can become linear.
This master guide explains the binary-search-tree invariant, comparisons, search paths, insertion, minimum and maximum, predecessor and successor, inorder traversal, deletion, height, degeneration, rotations, balanced-tree motivation, duplicates, recursive and iterative implementations, parent pointers, augmentation, complexity and the boundary between ordinary BSTs and specialised balanced families such as AVL and red-black trees.
Explore the eduKateSG How X Works library · How Computer Science Works | Master Edition · How Hash Tables Work
The Direct Answer: What a Binary Search Tree Is
A binary search tree, or BST, is a binary tree with an ordering rule. For a node with key k, keys in the left subtree compare before k and keys in the right subtree compare after k under the tree’s chosen ordering policy.
That local rule recursively applies to every subtree. The left subtree is itself a BST, and the right subtree is itself a BST.
This recursive ordering is what turns a tree from a shape into a search structure.
Binary Means at Most Two Child Links
Each node has at most a left child and a right child.
Binary does not mean balanced, complete or full. A node may have zero, one or two children, and the overall shape can be highly uneven.
Binary describes branching capacity; search-tree describes ordering.
The Ordering Invariant Is the Core Contract
If a key belongs left but is placed right, future search can follow the ordering rule and miss the key even though it exists physically.
The tree therefore remains useful only while every update preserves the invariant.
Search, insertion, deletion and rotation should all be understood as invariant-preserving transformations.
Comparison Defines the Tree’s Meaning
A BST needs a comparison relation over keys.
For numbers, ordinary numeric order is natural. For strings, lexicographic order might be used. For records, the tree may order by a chosen field or comparator.
The comparator is part of the data-structure contract.
The Comparator Should Behave Like a Consistent Ordering
If comparisons are inconsistent or change while keys remain in the tree, search paths can become invalid.
A key should not compare less than another today and greater tomorrow under the same logical tree state.
Stable ordering is to BSTs what stable hashing is to hash tables.
Search Turns Comparison Into Direction
At each node, compare the target key with the node key.
If equal, search succeeds. If smaller, continue into the left subtree. If larger, continue into the right subtree.
One comparison chooses one branch and discards the other from consideration.
Every Comparison Narrows the Search Region
At the root, all keys are possible. After moving left, every key greater than or equal to the root under the duplicate policy is excluded. Another comparison narrows again.
Search efficiency comes from repeatedly partitioning the ordered key space.
This is tree-shaped binary search.
Height Determines Search Cost
Search follows one root-to-node or root-to-null path.
The number of comparisons is therefore proportional to tree height h.
In a shallow balanced tree, h is O(log n). In a degenerate chain, h can be O(n).
A Binary Search Tree Is Not the Same as Binary Search
Binary search works on an indexed sorted sequence and repeatedly chooses the middle region.
A BST stores ordering in pointers or node links. The root is not necessarily the median unless balancing or construction guarantees it.
Both exploit order to discard possibilities, but their storage and update behaviour differ.
Insertion Is Search Until an Empty Link
To insert a new key, follow the same comparisons as search.
When the appropriate child link is null, place the new node there under the tree’s duplicate policy.
Search and insertion therefore share a path-selection mechanism.
Insertion Order Shapes the Tree
Insert 4,2,6,1,3,5,7 and the result can be nicely balanced.
Insert 1,2,3,4,5,6,7 into an ordinary unbalanced BST and each new key goes right, creating a chain.
The set of keys is identical; the insertion history changes performance.
A Sorted Input Can Be Worst-Case for a Naive BST
Monotonic insertion makes each new node a child of the previous extreme.
Height grows to n−1 rather than about log n.
This is the central reason balanced BST variants exist.
Minimum Means Follow Left Links
In a non-empty BST, the minimum key is found by repeatedly moving left until no left child remains.
Why? Every left move reaches a smaller region, and if no smaller left child exists at the final node, that node is minimum within the subtree.
This operation costs O(h).
Maximum Means Follow Right Links
The symmetric rule finds the maximum: keep moving right.
The rightmost node contains the greatest key under the comparator.
Again, cost follows height.
Inorder Traversal Produces Sorted Order
Inorder traversal visits left subtree, then node, then right subtree.
Because all left keys precede the node and all right keys follow it, inorder traversal outputs keys in sorted order under the BST invariant.
This is one of the strongest visible demonstrations that the ordering rule is globally coherent.
Traversal and Search Use the Same Structure Differently
Search chooses one branch using a target key. Inorder traversal deliberately visits both subtrees to enumerate the whole ordered set.
Same tree, different goal.
Search exploits pruning; traversal exploits structure.
Predecessor Means the Previous Key in Sorted Order
The predecessor of a node is the largest key smaller than it under the ordering policy.
If the node has a left subtree, its predecessor is the maximum of that left subtree.
If not, parent links or an ancestor search can identify the nearest ancestor for which the node lies in the right side.
Successor Means the Next Key in Sorted Order
The successor is the smallest key larger than the node.
If a right subtree exists, the successor is its minimum.
Otherwise, move upward until reaching an ancestor for which the node lies in the ancestor’s left side.
Parent Pointers Are Useful but Not Mandatory
A node can store links only to children, or also keep a parent pointer.
Parent links simplify upward navigation for predecessor, successor, deletion and some rotations.
They add memory and update obligations.
Recursive BST Code Mirrors the Data Structure
A BST is recursively composed of subtrees, so recursive search, insertion and traversal can be concise.
The base case is typically a null subtree or a matching key.
The previous recursion cluster explains why this structural recursion feels natural.
Iterative BST Code Avoids Call-Stack Depth
Search and insertion can be implemented with loops and explicit current/parent variables.
This avoids recursion depth issues in badly skewed trees.
The algorithmic path is the same; only the control representation changes.
Deletion Is the Hard Update
Search and insertion alter or follow one path. Deletion must remove a node while reconnecting the remaining subtrees so the ordering invariant survives.
The number of children determines the case.
This is why BST deletion is usually taught separately.
Deleting a Leaf Is Structurally Simple
A leaf has no children.
Remove the parent’s pointer to that leaf, or replace the root with null if it is the only node.
No descendant subtree needs reattachment.
Deleting a Node With One Child Is a Splice
If a node has only one child, connect the node’s parent directly to that child.
The child subtree already lies entirely on the correct side of the deleted node’s ancestors.
The node can be bypassed without changing relative key order.
Deleting a Node With Two Children Needs a Replacement
With two children, neither subtree can simply replace the node without care.
A standard solution chooses the inorder successor, the minimum node in the right subtree, or symmetrically the predecessor from the left subtree.
That replacement key lies exactly at the boundary needed to preserve order.
Why the Successor Has at Most One Child in Its Original Position
The successor chosen as the minimum of the right subtree cannot have a left child, or that child would be even smaller.
It may have a right child.
This makes removing the successor from its original location a simpler zero-or-one-child deletion.
Deletion Can Move Values or Move Nodes
One implementation copies the successor key/value into the target node and then deletes the successor node.
Another transplants nodes structurally.
The choice affects identity, references and augmentation metadata but not the abstract BST result.
Duplicate Keys Need a Policy
A BST may reject duplicates, store counts, store multiple values per key, or consistently place equal keys on one side.
The policy must be reflected in search, insertion, deletion and traversal semantics.
Unspecified duplicate handling creates subtle invariant ambiguity.
Multisets Can Store Counts
Instead of inserting a new node for every duplicate, a node can store a multiplicity count.
Deletion decrements the count until the final copy is removed structurally.
This keeps tree height tied to distinct keys rather than total multiplicity.
Maps Store Key-Value Pairs
A BST can implement an ordered map: nodes contain keys plus associated values.
Search compares keys but returns or updates values.
Ordering is by key; values need not be comparable.
Sets Store Only Keys
A BST set uses the same structure without separate mapped values.
Membership, insertion, deletion and ordered iteration are natural operations.
Tree-based sets can additionally support range and neighbour queries efficiently.
Range Queries Are a Major BST Strength
To list keys between low and high, the tree can prune subtrees that lie entirely outside the range.
A hash table has no natural sorted neighbourhood for this operation.
This is one reason ordered trees remain important despite hash maps.
Lower Bound and Upper Bound Fit the Tree
A lower-bound query seeks the first key not less than a target. An upper-bound query seeks the first key greater than a target under common conventions.
Search can keep a candidate ancestor while moving left or right.
Ordered neighbour queries emerge from the BST invariant.
Rank and Select Need Augmentation
An ordinary BST knows order but not automatically how many nodes lie in each subtree.
Store subtree sizes and update them after modifications; then the tree can answer rank and select queries efficiently when height is controlled.
This creates an order-statistics tree.
Augmentation Must Survive Every Update
Subtree size, aggregate sum, interval maximum or other metadata can be attached to nodes.
Insertion, deletion and rotation must recompute affected metadata.
Augmentation is powerful because local tree changes require only local metadata repair if the summary is designed well.
Height Is a Structural Property, Not a Stored Requirement
Height can be computed recursively, but balanced trees often store height or balance metadata to update it efficiently.
An ordinary BST need not store height at every node.
Whether metadata is explicit depends on the operations required.
Balanced Trees Control Height
AVL trees, red-black trees and other balanced families add invariants beyond ordinary BST ordering.
After updates, they use rotations and metadata or colouring rules to keep height logarithmic.
This cluster leaves those families for later standalone owners.
A Rotation Changes Shape Without Changing Sorted Order
A left or right rotation locally rearranges a parent-child relationship while preserving the inorder sequence of keys.
That makes rotation the fundamental shape-changing primitive of many balanced BSTs.
The dedicated rotation pillar explains why the order remains valid.
Balance Is About Path Length, Not Visual Symmetry
A perfectly symmetric tree is not required for logarithmic operations.
Balanced families allow bounded unevenness under specific rules.
The goal is to prevent height from drifting toward n.
Random Insertion Can Often Produce Reasonable Average Shape
Under suitable random-order assumptions, ordinary BST height is logarithmic in expectation up to constants.
But applications cannot always assume random insertion order.
Adversarial or naturally sorted data motivates explicit balancing.
Treaps Use Random Priorities for Probabilistic Balance
A treap combines BST ordering by key with heap ordering by random priority.
Rotations restore heap priority after insertion or deletion.
This yields expected logarithmic height under standard assumptions without deterministic balance metadata.
Splay Trees Reorganise Around Access
Splay trees rotate an accessed node toward the root.
They provide amortized guarantees and adapt to locality of reference rather than maintaining a strict per-node balance condition.
They are another example of rotations preserving order while changing shape.
AVL Trees Enforce a Strong Height-Balance Rule
AVL trees constrain the height difference between child subtrees and repair violations with rotations.
Their strict balance gives very short search paths.
This is a future standalone cluster rather than an owner absorbed here.
Red-Black Trees Encode Balance With Colour Rules
Red-black trees use node colours plus structural invariants to keep root-to-leaf paths within bounded ratios.
They also repair updates with recolouring and rotations.
Again, the ordinary BST ordering is the substrate; the colour rules add balance.
B-Trees Are Ordered Trees for a Different Storage Environment
B-trees allow many keys and children per node and are designed to reduce expensive storage-page accesses.
They are not binary search trees, though they share the high-level idea of ordered partitioning.
Databases and filesystems often favour B-tree families.
BST Search Versus Hash Lookup
Hash tables aim for expected O(1) exact lookup but do not naturally support ordering or range queries.
Balanced BSTs aim for O(log n) ordered operations and support predecessor, successor and range traversal.
Choose based on the operation mix, guarantees and ordering needs.
BST Search Versus Sorted Arrays
A sorted array supports O(log n) binary search and excellent memory locality.
Inserting or deleting in the middle can require shifting O(n) elements.
A tree trades some locality for cheaper structural updates when balanced.
BST Search Versus Heaps
A heap maintains enough order to access an extreme element efficiently but does not support arbitrary ordered search like a BST.
Heap structure is partial; BST structure supports directed search for any key.
Data structures encode only the order needed for their target operations.
BSTs and Recursion Are Conceptually Linked
Every subtree is a BST under the same invariant.
That self-similarity supports recursive algorithms and inductive correctness proofs.
The earlier recursion cluster provides the general execution model; BSTs give it a concrete ordered structure.
Correctness Proofs Follow the Invariant
Search correctness argues that when the target compares smaller than the current key, it cannot appear in the right subtree under the invariant.
Insertion correctness argues the new key is placed at the first empty location along its unique comparison path.
Deletion correctness argues reconnection or successor replacement preserves all left-before-node-before-right relationships.
A Search Path Is Unique Under a Strict Comparator
At each node, comparison chooses one of at most three outcomes: equal, left or right.
Therefore a target key has one deterministic search path through a valid BST.
This makes debugging easier: if an existing key is not found, either the comparator or invariant has been violated.
The Tree Does Not Know Global Rank Unless You Tell It
Ordinary node links encode relative order, not exact position among all keys.
Inorder traversal can recover global sorted order but costs O(n).
Augmented subtree sizes turn that implicit order into fast rank information.
Memory Layout Affects Real Performance
Pointer-based trees can suffer cache misses because nodes may be scattered across memory.
Array-based layouts, node pooling and B-tree-like blocking can improve locality.
Asymptotic O(log n) does not erase hardware effects.
Object Allocation Cost Matters
One heap allocation per node can be significant for small payloads.
Custom allocators or compact node arrays may improve performance.
The abstract BST does not dictate physical memory representation.
Concurrency Adds Structural Coordination
Concurrent search trees must handle rotations, insertions and deletions while readers and writers access nearby nodes.
Locks, optimistic validation or lock-free techniques may be used.
The simple invariant is the foundation; concurrent correctness is an additional layer.
Persistence Creates Versioned Trees
Functional or persistent BSTs can create a new version by copying only nodes along the modified path and sharing untouched subtrees.
Balanced persistent trees make immutable ordered maps practical.
Tree structure naturally supports structural sharing.
Path Copying Works Because Updates Are Local
Inserting or deleting touches a root-to-leaf path plus perhaps local rebalancing.
Unchanged subtrees can be reused between versions.
This is another benefit of recursive decomposition.
A Common Failure: Forgetting That Shape Controls Complexity
Code implements a correct BST and labels every operation O(log n).
Without a balance guarantee, height can be n.
Complexity should be stated as O(h), with h bounded separately if a balanced variant is used.
A Common Failure: Inconsistent Duplicate Policy
Insertion sends equal keys right, search stops at the first equal key, and deletion assumes uniqueness.
The structure behaves unpredictably as a multiset or map.
Choose and document duplicate semantics.
A Common Failure: Mutable Comparison Keys
A record is inserted by a field, then that field changes in place.
The node can now be on the wrong side of ancestors.
Remove and reinsert when the ordering key intentionally changes.
A Common Failure: Broken Parent Pointers
Child links are updated but the child’s parent pointer is not.
Predecessor, successor and rotations later follow stale structure.
Bidirectional links double the update obligations.
A Common Failure: Delete Two-Child Case Without Proper Replacement
The target node is removed and subtrees are reattached arbitrarily.
Some keys cross the ordering boundary and the invariant breaks.
Use a boundary key such as inorder successor or predecessor and preserve subtree relationships carefully.
A Common Failure: Rotation Loses the Middle Subtree
A left rotation moves a right child upward but forgets the child’s left subtree that must become the old node’s right subtree.
Nodes become disconnected or order breaks.
Rotations are local but exact pointer choreography matters.
A Common Failure: Metadata Not Updated
Tree structure is correct after insertion, deletion or rotation, but stored height, subtree size or aggregate values are stale.
Later balance or rank operations become wrong.
Structural and augmented invariants must be repaired together.
A Common Failure: Recursion Overflows on a Degenerate Tree
A recursive traversal works on balanced examples but crashes on a long chain.
Unbalanced BST height can be linear.
Use iterative traversal, explicit stacks or a balanced data structure when depth is not controlled.
Navigation Perspective: A BST Is a Landscape Where Every Signpost Deletes Half the Map Conceptually
At each node, the comparison tells you which side of the ordered world can still contain the target.
The tree does not need coordinates for every key; it needs a chain of ordering decisions.
Search is therefore navigation through inequalities.
Cross-Disciplinary Perspective: One Ordered Tree, Many Professional Uses
An algorithms student sees O(h). A language-library engineer sees ordered maps and sets. A database engineer sees the ancestor of B-tree indexing. A compiler engineer sees symbol or scope structures. A functional programmer sees persistent maps. A runtime engineer sees rotations and cache misses.
The roles differ, but the invariant remains left-before-node-before-right.
That invariant is the civilisation of the data structure: every operation must preserve the shared order.
A Practical BST Checklist
What comparator defines order? Are duplicates allowed? What is the current height? Is balance guaranteed or merely hoped for? Are parent pointers stored? Are nodes augmented with metadata? What happens on two-child deletion? Do rotations update every link and metadata field? Are keys mutable? Are range queries or predecessor/successor important enough to justify a tree over a hash table?
These questions reveal whether ‘use a BST’ is actually a complete design.
The tree’s value comes from operations, not from its shape alone.
How to Teach BSTs From First Principles
Begin with a sorted list and ask how comparison can discard keys. Then arrange the same comparisons as a decision tree.
Insert keys one by one and let students see how history changes shape. Run inorder traversal to prove that local left/right rules create global sorted order.
Only then introduce deletion and rotations, because both make sense as attempts to preserve the same invariant under structural change.
Frequently Asked Question: Is Every Binary Tree a BST?
No. A binary tree only limits each node to at most two children. A BST additionally satisfies an ordering invariant.
A binary heap is binary but follows a different ordering rule.
Frequently Asked Question: Is Every BST Balanced?
No. Ordinary BST insertion can produce a chain.
Balanced families add extra invariants and repair operations to bound height.
Frequently Asked Question: Why Is Search O(h)?
Search follows one path from the root toward a node or null link, visiting at most one node per level.
The number of levels visited is bounded by tree height h.
Frequently Asked Question: Why Does Inorder Traversal Sort the Keys?
It recursively visits every left subtree before its node and every right subtree after its node.
That matches the BST ordering invariant at every level.
Frequently Asked Question: Why Use a BST Instead of a Hash Table?
When sorted iteration, range queries, predecessor/successor or stronger logarithmic guarantees from a balanced variant matter, an ordered tree can be a better fit.
For pure exact lookup under suitable conditions, hash tables are often faster in expectation.
Frequently Asked Question: What Is the Difference Between a BST and a B-Tree?
A BST has at most two children per node. A B-tree stores multiple keys and children per node and is designed around block-oriented storage and high branching factors.
They are related ordered-search structures but solve different engineering constraints.
The Series Map
This master has three pillars. Search and Insertion explains comparison paths and ordered placement. Deletion explains leaf, one-child and two-child removal. Tree Rotations explains local rewiring that preserves sorted order and enables balancing.
AVL trees, red-black trees and B-trees remain separate future owners rather than being absorbed here.
Sources and Further Reading
For binary search trees, search, insertion and traversal, see MIT OpenCourseWare: Binary Search Trees, BST Sort.
For balanced binary search trees and rotations, see MIT OpenCourseWare: AVL Trees, AVL Sort.
For a current educational overview of binary search trees, see Cornell CS 2110 course materials.
Final Synthesis: A BST Turns Order Into Paths
A binary search tree stores more than values. It stores comparison decisions in its shape.
Every left edge means ‘smaller region’; every right edge means ‘larger region’. Search follows those inequalities, insertion extends them, deletion repairs them, inorder traversal reveals their sorted consequence, and rotations can change shape without changing the order they encode.
The tree is fast when those paths stay short—and that is why balance becomes the next layer of the story.
Worked BST Shape Comparisons: Same Keys, Different Histories
Median-First Insertion Produces Short Paths
Take keys 1 through 7. Insert 4 first, then 2 and 6, then 1, 3, 5 and 7. The result is a compact three-level tree. Search for any key needs only a few comparisons. Inorder traversal still returns 1,2,3,4,5,6,7, but now the shape also supports short root-to-key paths. This example separates the sorted set represented by the tree from the insertion history that produced its shape.
Sorted Insertion Produces the Same Order and a Very Different Cost
Insert 1,2,3,4,5,6,7 into an ordinary BST. Every new key moves right until it reaches the end. The inorder sequence is still exactly correct, yet the height becomes six edges instead of two under an edge-count convention. Search for 7 visits every node. The example demonstrates why BST correctness does not imply BST efficiency and why balance must be stated as a separate property.
Ordered Queries Beyond Exact Search
Range Search Uses Bounds to Prune Whole Subtrees
Suppose the task is to report every key from 30 through 50. At a node below 30, its entire left subtree is also below the lower bound and can be skipped. At a node above 50, its entire right subtree can be skipped. Only branches capable of intersecting the interval need traversal. A balanced BST can therefore answer ordered-range queries in time related to tree height plus the number of reported results.
Nearest-Key Queries Are Native to the Structure
Lower bound, upper bound, predecessor and successor all exploit the ordered path. During search, maintain the best candidate seen so far. Moving left can improve a too-large candidate; moving right can improve a too-small candidate. These operations explain why ordered trees remain valuable even when hash tables offer faster expected exact lookup: a hash table does not naturally know which key comes next.
BSTs as a Foundation for Larger Data-Structure Families
Balanced Trees Add Shape Invariants
AVL and red-black trees retain the same comparator and inorder semantics while adding rules that stop height from degenerating. The ordinary BST remains the semantic substrate: search still moves left or right, insertion still finds an ordered location, and deletion still preserves predecessor/successor relationships. Balance policy sits above those operations and repairs shape afterward.
Treaps and Splay Trees Change the Reason for Rotation
A treap adds random priority and rotates to preserve heap order. A splay tree rotates recently accessed nodes toward the root to obtain amortised adaptive behaviour. The same generic rotation primitive can therefore serve probabilistic balance, strict balance or access locality. This is why the BST cluster deliberately separates ordering from rotation mechanics: later families can reuse the same foundation without semantic duplication.
Complexity Should Be Written in Two Layers
First State O(h)
Exact search, insertion placement, minimum, maximum, predecessor, successor and structural deletion all follow one or a small number of root-to-descendant paths, so the honest ordinary-BST bound is O(h), where h is tree height. This statement remains correct for every shape.
Then State the Height Assumption
If construction or a balancing invariant guarantees h=O(log n), those operations become logarithmic. If input order is uncontrolled and no balancing exists, h can be O(n). Separating the operation bound from the structural bound prevents a common documentation mistake in which “BST” is silently treated as though it means “balanced BST.”
Production Invariants and Validation
Validate Global Bounds, Not Only Parent-Child Comparisons
A node can be greater than its parent and still violate the BST invariant relative to a more distant ancestor. A robust validator carries lower and upper bounds downward or checks that inorder traversal is monotonic under the comparator. This catches misplaced descendants that local parent-child tests can miss.
Validate Every Augmentation Separately
If nodes store subtree size, height, sums or interval summaries, recompute those values independently in test builds. A tree can remain perfectly searchable while its rank metadata is wrong. Data-structure correctness is a bundle of invariants; the BST ordering rule is the foundation, not the entire contract.
BST Design Review: Choose the Tree for the Queries You Actually Need
A binary search tree is most valuable when order is itself useful data. Exact lookup, lower bound, upper bound, predecessor, successor, sorted iteration and range reporting all derive from the same comparator structure. If the workload needs only exact membership, a hash table may be simpler and faster in expectation. If the workload is mostly sequential iteration with rare updates, a sorted array can offer better locality. If storage pages dominate, a B-tree family may be the natural structure.
The ordinary BST should therefore be understood as a reusable ordered-search substrate rather than a universal container. Its O(h) operations become strong guarantees only when another policy controls h. That is why AVL, red-black, treap and splay structures are extensions of the BST idea rather than replacements for it.
Continue the How X Works Series
How X Works Hub · How Computer Science Works · How Hash Tables Work
