The Core Idea
One Rule, Applied at Every Node
A binary search tree (BST) is a binary tree (each node has at most two children) that follows one ordering rule at every single node: everything in that node's left subtree is smaller than the node's value, and everything in its right subtree is larger. This rule isn't just true for the root — it holds recursively for every node in the tree, which is what makes searching so efficient.
Because of this rule, searching for a value follows exactly the same logic as binary search on a sorted array: compare the target to the current node, go left if smaller, go right if larger, and repeat. Each step eliminates an entire subtree from consideration — the same halving effect that makes binary search O(log n), applied to a tree instead of an array.
💡 Memory Trick
Picture a family tree of numbers where every parent silently enforces 'smaller kids on my left, bigger kids on my right' — and every one of those kids enforces the exact same rule among their own children. Looking for a number means starting at the top and, at each generation, asking 'am I too big or too small for this person' and stepping to the correctly-sized side.
The Core Operations
Search, Insert, Delete, and Traverse
1
Search — O(log n) average
Starting at the root, compare the target value to the current node. If equal, found it. If smaller, move to the left child; if larger, move to the right child. Repeat until found or you reach a null child (not present).
2
Insert — O(log n) average
Search for where the new value would logically be (following the same left/right rule), and when you reach a null spot, place the new node there. This never disturbs the existing structure — it just extends the tree at the correct leaf position.
3
Delete — O(log n) average, more involved
Deleting a leaf node is trivial — just remove it. Deleting a node with one child means replacing it with that child. Deleting a node with two children is trickier: replace its value with its in-order successor (the smallest value in its right subtree, found by going right once then left as far as possible), then delete that successor node from its original position.
4
In-Order Traversal — Visits Nodes in Sorted Order
Recursively visit the left subtree, then the current node, then the right subtree. Because of the BST ordering rule, this traversal always outputs every value in the tree in fully sorted order — a useful and non-obvious property that comes entirely free from the tree's structure.
The Critical Weakness
Why Balance Matters So Much
The O(log n) performance claimed above only holds if the tree is reasonably balanced — meaning its height stays close to log n as nodes are added. If values are inserted in already-sorted order (like inserting 1, 2, 3, 4, 5 one after another), every new node becomes the right child of the previous one, and the 'tree' degenerates into a straight line — effectively a linked list, with O(n) search, insert, and delete instead of O(log n).
This is exactly why self-balancing variants exist (AVL trees, Red-Black trees) — they perform extra rebalancing work during insertion and deletion specifically to guarantee the tree's height never grows large enough to lose the O(log n) advantage, regardless of what order values are inserted in.
🖥️ Applied Scenario
You're building a system that needs to store usernames and quickly check whether a given username is already taken, and you're deciding between a plain sorted array and a binary search tree.
1
You recognize a sorted array supports O(log n) search via binary search — good — but inserting a new username requires shifting every element after the insertion point, an O(n) cost per signup.
2
You choose a binary search tree instead, since both search and insertion are O(log n) on average — new signups don't force any large-scale shifting.
3
You then realize that if usernames were ever inserted in already-alphabetically-sorted order (say, from a bulk import of a pre-sorted list), your BST would degenerate into a straight line with O(n) operations.
4
Conclusion: to protect against that worst case, you choose a self-balancing variant (like a Red-Black tree) instead of a plain BST, guaranteeing O(log n) performance regardless of insertion order.
📌 Exam Application
Exam questions often ask you to trace through inserting or deleting a sequence of values into a BST by hand, drawing the resulting tree at each step. You may also be asked to identify the in-order successor of a given node (useful for two-child deletion), or to explain why a BST's worst-case complexity is O(n) despite its average case being O(log n) — the answer centers on unbalanced insertion order.
⚠️ Most Common Binary Search Trees Mistakes
The most common mistake is assuming BST operations are always O(log n) — that guarantee only holds for a balanced (or randomly-inserted) tree; a BST built from already-sorted input degenerates to O(n) for every operation, a frequently tested exam trap. Another frequent error, when deleting a node with two children, is forgetting to actually remove the in-order successor from its original location after copying its value up — leaving a duplicate node in the tree.
✓ Quick Self-Test
Can you insert the sequence 50, 30, 70, 20, 40, 60, 80 into a BST by hand and draw the resulting tree? Can you explain, step by step, what happens in memory when you delete a node with two children?
→
← All Data Structures Lessons