Skip to the content
Software Made Clear
About

Foundations · 5 nodes

Trees and traversal

Five steps from what a tree is to why databases put them on disk. Two of them are visualisers, so you build the shapes yourself before the prose explains them.

Is this path right for me?

ASSUMES

Nothing. This is the entry point.

GIVES YOU

The intuition that shape decides cost, which the whole Persistence path then leans on.

LEADS TO

Persistence, where the same tree ends up on a disk page.

Nothing is tracked and nothing is locked — the map exists so you can see where an article sits.

Suggested start Written Not written yet Optional or subtopic

  1. NODE 01 · REQUIRED Not written yet

    What a tree actually is

    • Nodes and edges
    • Depth and height

  2. NODE 02 · REQUIRED Suggested start

    Binary search trees

    Insert values one at a time and watch insertion order decide the shape of a binary search tree, and that shape quietly decide every lookup's real cost.

    • Insertion order
    • Degenerate shapes

  3. NODE 03 · REQUIRED Written

    Tree traversal orders

    Four traversal orders differ by one line of code — pick the right one on purpose and your sorted output, serialised tree, or shallow answer stops being luck.

    • Recursive walks
    • Explicit stacks

  4. NODE 04 · REQUIRED Written

    Balancing, and when it pays

    Insert values in sorted order and watch a plain search tree collapse into a list while an AVL tree beside it rotates and holds its height near log n.

    • Rotations
    • Amortised cost

  5. NODE 05 · REQUIRED Not written yet

    B-trees on disk

    • Page size and fan-out
    • Why depth stays small