Tree Algorithms
Walking, searching and rebalancing trees, where the height of the tree sets every cost.
Tree Traversals: Preorder, node before subtrees
A tree is a set of nodes where each one points to its children and nothing points back to the root. That single rule means any subtree is itself a tree, so almost every algorithm here is written once for a node and then called on the two halves below it. The recursion is not a trick for saving lines. It is the shape of the data.
A binary search tree adds a second rule: everything to the left of a node is smaller, everything to the right is larger. Now a search follows one path instead of visiting every node, and an inorder walk comes out sorted. Every cost in the category is written in terms of h, the length of that path, and h sits somewhere between log n for a full tree and n for a tree that grew into a line.
The balanced trees exist to hold h at log n. An AVL tree stores the height difference between a node's two sides and rotates as soon as it reaches two. A red-black tree uses one colour bit per node and a fix-up after each insert to keep the longest root-to-leaf path within twice the shortest. Both spend a constant amount of pointer work per insert so that every search afterwards stays cheap.
After this you can
- Produce the preorder, inorder, postorder and level order of a tree by hand
- Search, insert and delete in a binary search tree, including the two-child delete
- Say why a tree built from sorted input costs O(n) per search and what fixes it
- Apply a single and a double rotation, and say which imbalance calls for which
- Check a tree against the red-black rules and name the rule a violation breaks
In this order
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
- Level Order Traversal
- Zigzag Level Order
- Reverse Level Order
- BST Search
- BST Insert
- Find Minimum and Maximum
- Successor and Predecessor
- BST Delete
- Validate BST
- BST Range Search
- Lowest Common Ancestor
- BST from Sorted Array
- Balance Factor
- Left Rotation
- Right Rotation
- Left-Right and Right-Left Rotations
- AVL Insert with Rebalancing
- AVL Delete with Rebalancing
- Red-Black Rules
- Red-Black Insert Fix-up
- Red-Black Delete Fix-up
Also in this category
BST Operations
Tree Traversals
Where people go wrong
Validating a node against its parent only
A node can be larger than its parent and still break the tree, because an ancestor further up already fixed a tighter bound on that side. Each node inherits an interval from every ancestor, and the check has to carry that interval down.
Deleting a node with two children
There is no single child to splice in, so the node is not removed at all. Its inorder successor, the minimum of its right subtree, moves into the hole, and that successor is then deleted instead. By construction it has at most one child, so the second delete is the easy case.
Sorted input builds a line
Inserting 1 to n into a plain search tree gives height n and searches that walk every node. Sorted or nearly sorted input is common rather than rare, and it is the reason AVL and red-black trees do extra work on the way back up.