In a binary search tree, every left-subtree value is smaller than its node and every right-subtree value is larger. A search chooses left or right at each comparison, making a well-balanced tree efficient.
A simulator for insertion, lookup, and deletion in a binary search tree
1. Load an example or clear the tree
2. Enter a value and choose an operation
Insertion and lookup highlight the path from the root in orange. Build from sorted values to see the tree become skewed.
Find, insert, and delete
Start a search at the root, following the left child for a smaller value and the right for a larger one. Insertion follows the same path and adds a node at the first empty position.
Deletion depends on the number of children. Remove a leaf directly; replace a node with its only child; or, for two children, replace it with the minimum in its right subtree. This successor preserves the ordering property.
Tree shape determines performance
Worst-case search comparisons equal the tree height. A balanced tree with n nodes has height O(log n), but sorted insertion into an unbalanced tree creates a chain of height n. AVL and red-black trees use rotations and balancing rules to keep height O(log n).