A binary search tree maintains an ordering rule at every node, commonly smaller keys on the left and larger keys on the right, with a documented policy for duplicates. Search, insertion, and deletion follow that invariant; their cost depends on height rather than node count alone.
For every node, the left subtree contains smaller values and the right subtree contains larger values. The rule applies recursively to every subtree.
Each comparison chooses one side of the tree. If the tree is balanced, this discards about half the remaining nodes at each step.
Deletion has three cases: leaf, one child, and two children. Two-child deletion uses successor or predecessor replacement. Balanced trees keep height predictable.
Deleting a leaf removes it directly. Deleting a node with one child connects its parent to that child. For two children, replace the key with the inorder successor or predecessor and then delete that replacement node from its original position. Preserve attached values consistently, not only the key.
Operations average O(log n) only when height remains logarithmic. Sorted insertion can create a chain with O(n) operations. Use a balanced tree or standard library ordered map when worst-case performance matters.
An inorder traversal visits keys in sorted order when every node obeys the BST invariant. The minimum is the leftmost node and the maximum is the rightmost. A successor is the next key in inorder order; it is the leftmost node of the right subtree when that subtree exists.
| Need | Likely Structure | Reason |
|---|---|---|
| Teaching ordered search | Plain BST | Makes the invariant and degeneration visible. |
| Guaranteed ordered-map operations | Balanced search tree | Keeps height logarithmic. |
| Fast equality lookup only | Hash table | Ordering work is unnecessary. |
| Repeated smallest or largest item | Heap | Priority operations are the main goal. |
Root price 100. Search for 75:
75 < 100, go left.
75 > 60, go right.
75 found.
The ordering rule removes one side at every step.Each node must stay inside bounds inherited from every ancestor, not only its parent.
function isBst(node, low = -Infinity, high = Infinity) {
if (!node) return true;
if (node.value <= low || node.value >= high) return false;
return isBst(node.left, low, node.value) &&
isBst(node.right, node.value, high);
}
console.log(isBst({ value:10, left:{value:5}, right:{value:14,left:{value:9}} }));falseA binary tree limits children to two. A BST adds an ordering rule.
Explore 500+ free tutorials across 20+ languages and frameworks.