Binary Search Trees
A binary search tree is binary search made structural: instead of computing a midpoint, the shape of the data decides where to go next. That works beautifully when the tree is bushy and collapses to a linked list when it is not, which is why every serious implementation adds rebalancing on top.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
struct Node {
int val;
Node* left;
Node* right;
};
Node* insert(Node* root, int v) {
if (root == NULL) {
Node* n = new Node();
n->val = v; n->left = NULL; n->right = NULL;
return n;
}
if (v < root->val) root->left = insert(root->left, v);
else if (v > root->val) root->right = insert(root->right, v);
return root;
}
bool search(Node* root, int v) {
while (root != NULL) {
if (root->val == v) return true;
root = (v < root->val) ? root->left : root->right;
}
return false;
}
int main() {
Node* root = NULL;
int vals[7] = {50, 30, 70, 20, 40, 60, 80};
for (int i = 0; i < 7; i++) root = insert(root, vals[i]);
cout << search(root, 40) << ' ' << search(root, 45) << endl;
return 0;
}Insert returns the (possibly new) subtree root, which is what lets the caller reattach it with root->left = insert(...) and handles the empty-tree case for free.
How it works, step by step
The invariant is recursive, not local
Every value in a node's left subtree must be less than the node, and every value on the right greater — not just the immediate children, the entire subtree. This distinction is the source of the classic isValidBST bug and matters more than the definition suggests.
Search is one comparison per level
At each node you compare and pick a side, discarding the other subtree entirely. That is the same halving idea as binary search, except the split point is wherever the tree happens to put it rather than the exact middle.
Insertion always creates a leaf
The descent continues until it falls off the tree at a NULL, and the new node is attached there. No existing node ever moves, which makes insertion cheap but also means the tree's shape is entirely determined by insertion order.
Returning the subtree root does the linking
Because insert returns a Node*, the parent reassigns root->left or root->right with the result. For an existing subtree that is a no-op reassignment; for an empty one it attaches the new node. One return value covers both cases without any parent-pointer bookkeeping.
Height is the real complexity
Every operation costs O(h). Random insertion order gives h around log n; sorted insertion gives h equal to n. The gap between those two is the entire reason AVL and red-black trees exist.
Complexity
Cost tracks the tree's height rather than its size, and height depends entirely on insertion order; feeding a plain BST already-sorted data produces a chain where every operation is a linear scan.
Common bugs
Validating a BST by comparing only with children
Checking node->left->val < node->val at each node accepts invalid trees. A node with value 6 in the left subtree of a root of 5 passes every local check but violates the global ordering. Validation must carry a (min, max) range down the recursion, narrowing it at each step.
Inserting sorted data
Inserting 1,2,3,...,n gives every node only a right child — a linked list with extra pointers. Search becomes O(n) and any recursive traversal risks a stack overflow. Insert 1 through 10 in order in DryRun and watch the tree render as a single descending chain — the clearest possible demonstration of why balancing exists.
Forgetting to reassign the result of insert
Calling insert(root->left, v); without assigning back to root->left builds the new node correctly and then discards the pointer to it. The tree never grows past its first node, and every element you inserted is leaked.
Not handling duplicate values
This implementation silently ignores duplicates because neither the < nor the > branch fires. That may be what you want, but if you expected a count or a second copy, elements will vanish with no error. Decide explicitly: ignore, keep a count in the node, or send equals consistently to one side.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What makes a binary tree a binary search tree?
Every node's entire left subtree contains only smaller values and its entire right subtree only larger ones, applied recursively at every node. The word entire is the important part — checking only the immediate children is not sufficient and accepts trees that break the ordering.
Why is BST search O(log n) only sometimes?
Because search cost equals the tree's height, and height depends on insertion order. Randomly ordered inserts produce a roughly balanced tree with height around log n, but sorted inserts produce a single chain of height n, making every search a linear scan. Self-balancing trees like AVL and red-black guarantee log n height regardless of input.
What happens if you insert sorted data into a BST?
You get a degenerate tree — effectively a linked list, since each new value is larger than everything before it and always goes right. All operations degrade to O(n), and recursive traversals can overflow the call stack on large inputs. This is the single most common way a BST-based solution becomes unusably slow.
How do you find the minimum value in a BST?
Follow left pointers from the root until a node has no left child; that node holds the minimum. The BST property guarantees nothing smaller exists anywhere else in the tree. The maximum is the mirror image — keep going right.