Data structures · intermediate
Tree and binary search tree
A tree is a hierarchy of nodes connected without cycles; a binary search tree gives each node at most two children and orders keys before or after it on consistent sides, with duplicate handling defined by the implementation.
Why it matters
Trees model hierarchy, while a balanced search tree maintains ordered lookup and range traversal without requiring a contiguous sorted array.
Mental model
How to reason about tree and binary search tree
Each comparison in a search tree chooses one subtree and discards the other. Performance follows height: logarithmic when balanced, linear when the tree degenerates into a chain.
Analogy
A choose-your-own-path directory asks one comparison at each junction. Balanced choices halve the remaining directory; one-sided choices become a long corridor.
Examples
See the boundary, not just the happy path
Worked example · Search by ordering
target 42 < node 50, so search only the left subtreeThe BST invariant proves the right subtree cannot contain 42, allowing it to be skipped.
Worked example · Sorted traversal
inorder(node) = inorder(left), visit(node), inorder(right)For a valid BST, in-order traversal emits keys in sorted order in Theta(n) time.
Useful contrast · Degenerate insertion order
insert 1, 2, 3, 4, 5 into an unbalanced BSTEvery node becomes a right child, height reaches n, and lookup loses logarithmic behavior.
Common mistakes
Misconceptions to remove early
Calling every binary tree a BST
Two children define a binary tree; the ordering invariant defines a binary search tree. A heap is binary-shaped but does not provide BST ordering.
Promising O(log n) without balance
BST operations are O(height). Only a balancing policy or favorable shape keeps height logarithmic.
Quick check
Can you predict the result?
1. What variable directly controls lookup cost in a binary search tree?
- • The tree's height
- • The byte size of each key
- • Whether traversal is written recursively
2. Why does in-order traversal of a BST produce sorted keys?
Keep building