Binary Search Trees: Ordered in O(log n)

A sorted array lets you binary-search in O(log n), but inserting a new value means shoving everything after it over by one, which is O(n). A hash map inserts fast but throws away all order. A binary search tree is the structure that keeps both: ordered data that still takes new values in O(log n). The trick is a single rule, applied at every node.

The one rule: left < node < right

A binary tree is just nodes, each pointing at up to two children, a left and a right. A binary search tree adds one invariant that holds at every node:

• everything in its left subtree is smaller than it,
• everything in its right subtree is larger.

That's it. Insert the values 5, 3, 8, 1, 4, 7, 9 in that order and the rule decides where each one lands. 5 is the root. 3 is smaller, so it goes left. 8 is larger, so it goes right. 1 is smaller than 5 (go left) and smaller than 3 (go left again). Every value walks down from the root, turning left or right based on the comparison, until it finds an empty spot.

That walk is the whole point. Searching for a value follows the same path: compare at the root, go left if you're smaller or right if you're larger, and repeat. Each step throws away half the remaining tree, exactly like binary search on an array, except now you can insert in the same O(log n) walk.

See the search walk

The tree below is built from 5, 3, 8, 1, 4, 7, 9. Step through a search for 7 and watch it compare at each node and pick a direction instead of scanning every value.

Look at the path it takes. 7 against 5: larger, go right to 8. 7 against 8: smaller, go left to 7. Found, in two comparisons, on a tree of seven nodes. The nodes it never touched (the entire left subtree under 3) were ruled out the instant 7 turned right at the root. That's the O(log n) saving: each comparison halves what's left to look at.

Inorder traversal comes out sorted

Here's the quietly beautiful part. Visit a BST "inorder" (left subtree, then the node, then right subtree, applied recursively) and the values come out in sorted order, for free. No sorting step. The invariant already arranged them.

Why it works falls straight out of the rule: at any node, everything smaller is on the left and everything larger is on the right. So if you fully drain the left side before printing the node, then drain the right side after, you're guaranteed to emit values smallest-first. Apply that recursively all the way down and the whole tree streams out in order.

That makes a BST a structure you can keep and read back sorted whenever you want, something neither a hash map nor an unsorted array gives you.

Build one and search it

Here's a tiny BST in Python: an insert that follows the rule, a search that walks the same path, and an inorder that yields sorted values. Run it, then add your own numbers or change what you search for.

The insert and search functions are mirror images: both compare against the current node and recurse left or right. inorder does its work by ordering the recursion itself: drain left, emit, drain right. Notice the output is [1, 3, 4, 5, 7, 8, 9] even though you inserted them out of order.

The catch: shape decides speed

That O(log n) assumes the tree is balanced, short and bushy, so halving really does cut the work down to a logarithm. But the BST rule says nothing about shape. Insert values in already-sorted order (1, 3, 4, 5, 7, 8, 9) and every value is larger than the last, so it always goes right. The tree degenerates into a single long chain, basically a linked list. Now searching is O(n), because there's no left side to throw away. Same rule, worst possible shape.

This is why production code reaches for self-balancing trees, like red-black trees and AVL trees, that rebalance on every insert to keep the height logarithmic. Python's standard library doesn't ship one, but dict and set (hashing) cover most lookup needs, and bisect handles sorted lists. The plain BST is what you build to understand the idea. The balanced variants are what you reach for when the guarantee has to hold.

Where this leaves you

A BST is one rule (left smaller, right larger) applied at every node, and that rule buys you O(log n) search and insert on a balanced tree plus a sorted readout for free via inorder traversal. The catch is the catch of all trees: the guarantee lives in the shape, and a skewed tree throws it away.

Trees branch in two directions. Next we generalize to structures that can point anywhere: nodes connected by edges in any pattern at all. Next: Graphs & Traversal: BFS and DFS. If the recursion in insert and inorder felt shaky, double back to Recursion & the Call Stack, or brush up on the Python classes the Node here is built from.