Each node keeps smaller values on its left, larger on its right - so search zig-zags down.
at each node: go left if target < node, right if target > node, stop if equal
Frequently asked questions
Is a BST like playing 20 Questions?
Yes - each node is a yes/no question that sends you down the left or right branch, narrowing toward the answer. In a BST, 'is your target smaller or larger than this node?' plays the role of the question: smaller goes left, larger goes right, and one comparison discards an entire branch. Like a good game of 20 Questions, a balanced tree reaches any answer in about log(n) questions - though a badly built tree (questions in a poor order) can degrade to a long single line.
Why can a BST search be O(log n) sometimes and O(n) other times?
It depends entirely on the tree's shape, which depends on insertion order. If values arrive in a mixed order, the tree stays bushy and balanced, with height about log(n), so each search makes roughly log(n) comparisons. But if values arrive already sorted - 1, 2, 3, 4... - each new value attaches to the right of the last, and the 'tree' degenerates into a straight line of n nodes. Searching that line is just linear search, O(n). This fragility is exactly why self-balancing trees were invented.
How does a BST search decide which way to go at each node?
It uses the ordering invariant. At each node it compares the target with the node's key: if they are equal, it is found; if the target is smaller, it must be in the left subtree (everything left is smaller), so it goes left; if larger, it goes right. Because one comparison eliminates an entire subtree, the search descends a single path from root to leaf rather than exploring the whole tree - the tree version of binary search's halving.
How is a BST different from a sorted array with binary search?
They share the same idea - ordered data, halve the search each step - but a sorted array is static and a BST is dynamic. Inserting into a sorted array means shifting elements (O(n)); inserting into a BST is just relinking a pointer (O(log n) in a balanced tree). So when data changes frequently, a BST keeps both search and update fast, whereas a sorted array makes search fast but updates slow. The trade is that a BST uses extra memory for pointers and can become unbalanced.
What operations does a BST support besides search?
Insertion (find where the key belongs and link a new node), deletion (unlink a node and reconnect its children, the trickiest case), finding the minimum (follow left pointers to the end) and maximum (follow right), and an in-order traversal that visits keys in sorted order for free. This combination - fast search plus ordered traversal plus cheap updates - is why BSTs and their balanced variants underpin ordered maps and sets in many standard libraries.
Why do real libraries use balanced trees instead of plain BSTs?
Because a plain BST gives no guarantee against the degenerate O(n) line. Real-world data is often partly sorted, which is exactly the bad case. Self-balancing variants like AVL and red-black trees automatically restructure themselves on insert and delete so the height stays around log(n) no matter the input order. That guarantees O(log n) operations always, which is why std::map, Java's TreeMap, and the Linux kernel use red-black trees rather than naive BSTs.