After reading this
- Insert while preserving invariants
- Traverse in order
- Understand imbalance risk
A recursive rule
Every node is the root of another tree. To insert, compare, choose left or right, and repeat until an empty spot appears.
js
function insert(node, value) {
if (!node) return { value, left: null, right: null };
if (value < node.value) node.left = insert(node.left, value);
if (value > node.value) node.right = insert(node.right, value);
return node;
}Traversal reveals order
Walking left, node, and right produces sorted values. It follows directly from the invariant.
js
function inOrder(node, result = []) {
if (!node) return result;
inOrder(node.left, result);
result.push(node.value);
return inOrder(node.right, result);
}A tree can become a list
Inserting already sorted values creates one long branch. Search drops from O(log n) to O(n). AVL and red-black trees rebalance.
BST visualizer● interactive
8
310
1614
47
Try the worst case
Compare the trees produced by 5, 3, 8, 2, 4 and by 2, 3, 4, 5, 8.
Show a hint
Look at each tree's maximum height.