AlgoScope

Tree Algorithms

Walking, searching and rebalancing trees, where the height of the tree sets every cost.

26 topics6 lessons4 families

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
20304050✓607080current

50 is the root, and preorder writes a node down before going anywhere.

Open in the player →or start at step 2

In this order

  1. Preorder TraversalWrite the node down first, then walk its left subtree and then its right.
  2. Inorder TraversalLeft subtree, then the node, then the right. On a search tree that comes out sorted.
  3. Postorder TraversalFinish both subtrees before writing the node down, so the root comes last.
  4. Level Order TraversalWalk depth by depth with a queue rather than the call stack.
  5. Zigzag Level OrderLevel order with the reading direction flipped on every level.
  6. Reverse Level OrderLevel order pushed onto a stack, right child first, then popped: bottom level first, left to right.
  7. BST SearchCompare with the node, go left if smaller, right if larger.
  8. BST InsertSearch for the value and hang a new leaf wherever the search runs out of tree.
  9. Find Minimum and MaximumThe minimum is all the way left and the maximum all the way right. One path each.
  10. Successor and PredecessorThe next value up is the last node you turned left at, or the minimum of the right subtree.
  11. BST DeleteA leaf just goes, one child is spliced past, two children need a successor.
  12. Validate BSTEvery node must sit inside a window inherited from all its ancestors, not just its parent.
  13. BST Range SearchReport every value in a range, entering only the subtrees that could hold one.
  14. Lowest Common AncestorWalk down while both values are on the same side. Where they split is the answer.
  15. BST from Sorted ArrayTake the middle as the root and recurse on both halves, for a tree of height log n.
  16. Balance FactorLeft height minus right height. Every node must stay within -1, 0 or 1.
  17. Left RotationThe right child comes up and the old node drops to its left.
  18. Right RotationThe left child comes up and the old node drops to its right.
  19. Left-Right and Right-Left RotationsA zig-zag needs two rotations. Straighten the child first, then rotate the node.
  20. AVL Insert with RebalancingInsert as a BST, walk back up updating heights, and rotate the first unbalanced node.
  21. AVL Delete with RebalancingDelete like a BST, then rebalance every ancestor; unlike insert, several rotations may be needed.
  22. Red-Black RulesRoot black, no red under red, equal black count on every path; checked bottom-up by black height.
  23. Red-Black Insert Fix-upRed uncle: recolour and move up; black uncle: one or two rotations plus a recolour, then stop.
  24. Red-Black Delete Fix-upRemoving a black node creates a "double black" that is pushed up or resolved by sibling cases.

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.

Or a different category

Graph Traversal

The structure has cycles, or more than one route to the same node, so you need a visited set.

Heap Algorithms

You only ever want the smallest or largest element and never the order in between.

Lessons that teach these