Part 6 of 14

Trees and Heaps

Tree traversals, BSTs, balanced trees, heaps, priority queues, tries. The most-asked topic class in mid-level interviews.

Chapters
11
Hours
3
Difficulty
Intermediate
  1. 6.0beginner

    Binary tree fundamentals

    Tree terminology, height vs depth, the two physical representations, and the on-disk vocabulary every later Part 6 chapter assumes you have pinned down.

    20 min
  2. 6.1intermediate

    Tree traversals: pre, in, post

    One recursive skeleton has three positions for the visit() call. The pre, in, and post placements solve different problem families on the same scaffolding.

    20 min
  3. 6.2advanced

    Morris traversal: O(1)-space inorder by threading

    Walk a binary tree in inorder with no recursion stack and no auxiliary memory by threading temporary right-pointers from each subtree's rightmost descendant back to its successor.

    20 min
  4. 6.3intermediate

    Level-order traversal: BFS on trees

    BFS on trees, with the level_size = len(queue) snapshot that turns 'visit every node' into 'visit every node grouped by depth' with the boundaries preserved.

    15 min
  5. 6.4intermediate

    Heaps and priority queues

    Sift-up and sift-down, Floyd's O(n) bottom-up build vs O(n log n) repeated insert, and the language-by-language API for the priority-queue primitive.

    30 min
  6. 6.5intermediate

    Binary search trees

    The BST invariant, search/insert/delete operations, and why every shipping standard library uses a balanced variant instead of a plain BST.

    15 min
  7. 6.6advanced

    AVL trees and rotations

    Self-balancing BSTs from first principles: the AVL invariant, the four rotation cases, the 1.44 log(n+2) height bound, and why every production ordered map descends from this 1962 paper.

    20 min
  8. 6.7intermediate

    Red-black trees: an overview

    The balancing scheme behind TreeMap, std::map, and the Linux scheduler. Five invariants, the rotation cases at a high level, and what an interview can reasonably ask about them.

    15 min
  9. 6.8intermediate

    Tries

    Children-map-plus-end-flag nodes give prefix walks in O(L) on query length. The autocomplete and IP-routing problem family where prefix structure is the whole point.

    15 min
  10. 6.9intermediate

    Tree DP primer: post-order with side state

    Post-order helpers thread side state down through arguments, return aggregates up the call stack, and use a global to track diameter-style through-this-node optima.

    20 min
  11. 6.10advanced

    Segment trees

    O(log n) point updates and O(log n) range queries on the same array. The recursive build and the lazy-propagation extension for range updates.

    20 min