Binary Search Trees
Every node keeps smaller values to its left and larger values to its right, so a search can throw away half the tree at every step.
Loading visual…
Definition
A binary search tree is a binary tree with one extra rule: for every node, every value in its left subtree is smaller than the node's own value, and every value in its right subtree is larger. That single ordering rule is what makes the tree searchable. To look for a value, start at the root and compare: if the target is smaller, the whole right subtree can be ignored and the search moves left; if it is larger, the whole left subtree can be ignored and the search moves right; if it matches, the search is done. Each comparison throws away one whole half of what is left to check, the same idea as binary search on a sorted array, except the tree shape lets values also stay in the middle of a growing structure instead of a fixed array. The cost of a search, insert, or delete is proportional to the tree's height, not the number of nodes in it. A balanced tree keeps its height close to log2(n), so those operations run in O(log n). But nothing about a plain binary search tree forces it to stay balanced: inserting values that already come in sorted order builds a tree that leans entirely to one side, node after node with only a right child, which degenerates into a straight line and turns every operation into an O(n) walk, the same cost as searching an unsorted list. Self-balancing variants like AVL trees and red-black trees exist specifically to guarantee the O(log n) case regardless of insertion order.
Examples
function bstSearch(node, target) {
if (!node) return null;
if (target === node.value) return node;
return target < node.value ? bstSearch(node.left, target) : bstSearch(node.right, target);
}Comparing target against the current node rules out an entire subtree with each call, so the search only ever walks one path from the root to the target's position.
function bstInsert(node, value) {
if (!node) return { value, left: null, right: null };
if (value < node.value) node.left = bstInsert(node.left, value);
else node.right = bstInsert(node.right, value);
return node;
}The same left-smaller, right-larger comparison used for searching decides which side the new value belongs on, all the way down until it finds an empty spot.
function inOrder(node, out = []) {
if (!node) return out;
inOrder(node.left, out);
out.push(node.value);
inOrder(node.right, out);
return out;
}
// for a BST, inOrder always returns values in ascending sorted orderVisiting left, then the node, then right always yields smaller values before larger ones, so an in-order traversal of a BST reads the values back out in sorted order for free.
Common mistakes
- Inserting already-sorted data into a plain BST and ending up with a degenerate, linked-list-shaped tree with O(n) operations.
- Comparing values with the wrong direction (going right instead of left for a smaller value), which searches or inserts into the wrong subtree.
- Assuming a BST is always balanced; balance is only guaranteed by self-balancing variants like AVL or red-black trees.
Key takeaways
- Left subtree smaller, right subtree larger: that single rule is what makes a BST searchable.
- Search, insert, and delete all run in O(height), which is O(log n) when the tree is balanced and O(n) when it degenerates into a line.
- An in-order traversal of a BST always produces values in sorted order.
Searching a BST for a value that turns out to be larger than the current node. Which way does the search go?
Where you see this
- Implementing an ordered set or map that supports fast lookup, insert, and range queries.
- Databases and file systems use balanced search trees (B-trees, a wide variant) to index records.
- Autocomplete and spell-check style range lookups, finding all values between two bounds.
- Any place that needs sorted order maintained incrementally, without re-sorting after every insert.