Chapter 24: Trees and Graphs: Hierarchical and Network Data Structures

"The most important property of a program is whether it accomplishes the intention of its user." — C. A. R. Hoare

The data structures we have studied so far — arrays, records, linked lists — are fundamentally linear. They organize data in sequences: one element after another, in a line. This is adequate for many problems, but the world is not linear. Organizational charts are hierarchical. Road networks are interconnected webs. File systems are trees of directories within directories. Social networks are dense tangles of friendships and connections. To model these structures faithfully, we need data structures that capture hierarchy and connectivity.

This chapter introduces two such structures: trees and graphs. Trees represent hierarchical relationships — where every element has exactly one parent (except the root) and zero or more children. Graphs represent arbitrary connections — where any element can be connected to any other. Together, trees and graphs are the most versatile data structures in computer science, and the algorithms that operate on them — traversal, search, shortest path — are among the most important you will ever learn.

We will build binary trees and binary search trees from scratch, implement all three traversal orders, and learn to insert, search, and delete nodes. Then we will broaden our view to graphs, implementing adjacency matrices and adjacency lists, breadth-first search, depth-first search, and Dijkstra's shortest-path algorithm. Along the way, PennyWise gains a formal category tree, and Crypts of Pascalia's dungeon map becomes a graph with pathfinding.

Prerequisites: Pointers and dynamic allocation (Chapter 14), linked lists (Chapter 15), and recursion (Chapter 22) are essential. Trees and graphs are built from pointer-linked nodes, and nearly every algorithm in this chapter is recursive.

24.1 Trees: Hierarchical Data

A tree is a data structure consisting of nodes connected by edges, with two defining properties:

1. There is exactly one distinguished node called the root, which has no parent.
2. Every other node has exactly one parent and zero or more children.

These two rules guarantee that there are no cycles (you can never follow edges from a node back to itself) and that there is exactly one path from the root to any node.

Terminology

• Root: The topmost node (no parent).
• Leaf: A node with no children.
• Internal node: A node with at least one child.
• Parent / Child: If node A has an edge to node B below it, A is B's parent and B is A's child.
• Sibling: Nodes that share the same parent.
• Depth: The number of edges from the root to a node. The root has depth 0.
• Height: The number of edges on the longest path from a node to a leaf. A leaf has height 0. The tree's height is the root's height.
• Subtree: A node and all of its descendants form a subtree.

A Visual Example

           Company (root)
          /        \
    Engineering    Sales
    /     \          \
 Backend  Frontend  Regional
  / \       |       /    \
API  DB   React   East   West

This tree has height 3, depth 0 at the root, depth 3 at API/DB/React/East/West. Engineering and Sales are siblings. Backend is a child of Engineering and a parent of API and DB.

Trees in Computing

Trees appear everywhere:

• File systems: Directories contain subdirectories and files.
• HTML/XML documents: Tags are nested inside other tags.
• Expression trees: Mathematical expressions parsed into operator/operand trees.
• Decision trees: Machine learning models that classify data by branching.
• Category hierarchies: PennyWise's expense categories form a tree (Chapter 22).

24.2 Binary Trees (Structure, Traversal: In-order/Pre-order/Post-order)

A binary tree is a tree where every node has at most two children, conventionally called the left child and the right child.

Pascal Implementation

type
  PBTreeNode = ^TBTreeNode;
  TBTreeNode = record
    Data: Integer;
    Left, Right: PBTreeNode;
  end;

Creating Nodes

function NewNode(Value: Integer): PBTreeNode;
var
  Node: PBTreeNode;
begin
  New(Node);
  Node^.Data := Value;
  Node^.Left := nil;
  Node^.Right := nil;
  NewNode := Node;
end;

Tree Traversals

The three classic traversals differ only in when the current node is "visited" relative to its subtrees:

In-order (Left, Visit, Right):

procedure InOrder(Node: PBTreeNode);
begin
  if Node <> nil then begin
    InOrder(Node^.Left);
    Write(Node^.Data, ' ');
    InOrder(Node^.Right);
  end;
end;

Pre-order (Visit, Left, Right):

procedure PreOrder(Node: PBTreeNode);
begin
  if Node <> nil then begin
    Write(Node^.Data, ' ');
    PreOrder(Node^.Left);
    PreOrder(Node^.Right);
  end;
end;

Post-order (Left, Right, Visit):

procedure PostOrder(Node: PBTreeNode);
begin
  if Node <> nil then begin
    PostOrder(Node^.Left);
    PostOrder(Node^.Right);
    Write(Node^.Data, ' ');
  end;
end;

Traversal Trace-Through

Consider this binary tree:

        50
       /  \
     30    70
    / \   / \
   20  40 60  80

Let us trace each traversal in full detail.

In-order traversal (Left, Visit, Right):

InOrder(50)
  InOrder(30)
    InOrder(20)
      InOrder(nil) → return
      Visit 20
      InOrder(nil) → return
    Visit 30
    InOrder(40)
      InOrder(nil) → return
      Visit 40
      InOrder(nil) → return
  Visit 50
  InOrder(70)
    InOrder(60)
      InOrder(nil) → return
      Visit 60
      InOrder(nil) → return
    Visit 70
    InOrder(80)
      InOrder(nil) → return
      Visit 80
      InOrder(nil) → return

Output: 20 30 40 50 60 70 80  (sorted order for a BST!)

Pre-order traversal (Visit, Left, Right):

PreOrder(50)
  Visit 50
  PreOrder(30)
    Visit 30
    PreOrder(20)
      Visit 20
      PreOrder(nil) → return
      PreOrder(nil) → return
    PreOrder(40)
      Visit 40
      PreOrder(nil) → return
      PreOrder(nil) → return
  PreOrder(70)
    Visit 70
    PreOrder(60)
      Visit 60
      ...
    PreOrder(80)
      Visit 80
      ...

Output: 50 30 20 40 70 60 80  (root first — useful for copying trees)

Post-order traversal (Left, Right, Visit):

Output: 20 40 30 60 80 70 50  (leaves first — useful for deleting trees)

💡 Intuition: Why Three Traversals? Each traversal answers a different question. In-order asks: "What are the elements in sorted order?" Pre-order asks: "How is the tree structured from the top down?" (useful for serializing a tree). Post-order asks: "How can I process children before their parents?" (useful for computing sizes, freeing memory, evaluating expression trees where operators are internal nodes and operands are leaves).

Level-Order Traversal (BFS on a Tree)

There is a fourth traversal that visits nodes level by level, from top to bottom, left to right. This is essentially BFS applied to a tree:

procedure LevelOrder(Root: PBTreeNode);
var
  Queue: array[0..255] of PBTreeNode;
  Front, Rear: Integer;
  Current: PBTreeNode;
begin
  if Root = nil then Exit;
  Front := 0;
  Rear := 0;
  Queue[Rear] := Root;
  Inc(Rear);

  while Front < Rear do begin
    Current := Queue[Front];
    Inc(Front);
    Write(Current^.Data, ' ');
    if Current^.Left <> nil then begin
      Queue[Rear] := Current^.Left;
      Inc(Rear);
    end;
    if Current^.Right <> nil then begin
      Queue[Rear] := Current^.Right;
      Inc(Rear);
    end;
  end;
end;

For the tree above, level-order produces: 50 30 70 20 40 60 80.

Expression Trees

A particularly important application of binary trees is the expression tree, where internal nodes are operators and leaf nodes are operands. The expression (3 + 4) * (5 - 2) becomes:

        *
       / \
      +   -
     / \ / \
    3  4 5  2

The beauty of expression trees is that the three traversals produce three common notations:

• In-order: 3 + 4 * 5 - 2 (infix notation — though parentheses are needed for correct grouping)
• Pre-order: * + 3 4 - 5 2 (prefix/Polish notation — no parentheses needed)
• Post-order: 3 4 + 5 2 - * (postfix/Reverse Polish notation — no parentheses needed)

Evaluating an expression tree uses post-order traversal: evaluate the left subtree, evaluate the right subtree, then apply the operator at the root:

function EvalTree(Node: PBTreeNode): Integer;
begin
  if Node^.Left = nil then    { Leaf: must be a number }
    EvalTree := Node^.Data
  else begin                   { Internal: must be an operator }
    case Chr(Node^.Data) of
      '+': EvalTree := EvalTree(Node^.Left) + EvalTree(Node^.Right);
      '-': EvalTree := EvalTree(Node^.Left) - EvalTree(Node^.Right);
      '*': EvalTree := EvalTree(Node^.Left) * EvalTree(Node^.Right);
    end;
  end;
end;

Let us trace the evaluation of (3 + 4) * (5 - 2):

EvalTree(*)
  Left:  EvalTree(+)
           Left:  EvalTree(3) → 3 (leaf)
           Right: EvalTree(4) → 4 (leaf)
           Result: 3 + 4 = 7
  Right: EvalTree(-)
           Left:  EvalTree(5) → 5 (leaf)
           Right: EvalTree(2) → 2 (leaf)
           Result: 5 - 2 = 3
  Result: 7 * 3 = 21

The post-order traversal naturally evaluates the expression bottom-up: compute the operands first, then apply the operator. This is why post-order is also called "evaluate" order for expression trees.

Expression trees connect to the recursive descent parser we saw in Chapter 22. The parser builds the tree; the evaluator traverses it. This is the foundation of how compilers work: parse source code into a tree (the abstract syntax tree or AST), then traverse the tree to generate machine code.

Counting Nodes and Computing Height

Two more useful recursive operations on binary trees:

function TreeSize(Node: PBTreeNode): Integer;
begin
  if Node = nil then
    TreeSize := 0
  else
    TreeSize := 1 + TreeSize(Node^.Left) + TreeSize(Node^.Right);
end;

function TreeHeight(Node: PBTreeNode): Integer;
var
  LH, RH: Integer;
begin
  if Node = nil then
    TreeHeight := -1   { Convention: empty tree has height -1 }
  else begin
    LH := TreeHeight(Node^.Left);
    RH := TreeHeight(Node^.Right);
    if LH > RH then TreeHeight := 1 + LH
    else TreeHeight := 1 + RH;
  end;
end;

For the BST [20, 30, 40, 50, 60, 70, 80], TreeSize returns 7 and TreeHeight returns 2 (for a balanced tree) or 6 (for a degenerate tree).

24.3 Binary Search Trees (Insert, Search, Delete)

A binary search tree (BST) is a binary tree with a crucial ordering property: for every node N, all values in N's left subtree are less than N's value, and all values in N's right subtree are greater than N's value.

This property enables efficient search: at each node, we can eliminate half the remaining values by going left or right.

BST Search

function BSTSearch(Node: PBTreeNode; Target: Integer): PBTreeNode;
begin
  if Node = nil then
    BSTSearch := nil
  else if Target = Node^.Data then
    BSTSearch := Node
  else if Target < Node^.Data then
    BSTSearch := BSTSearch(Node^.Left, Target)
  else
    BSTSearch := BSTSearch(Node^.Right, Target);
end;

Time complexity: O(h) where h is the height of the tree. For a balanced tree, h = O(log n). For a degenerate tree (essentially a linked list), h = O(n).

Step-by-Step BST Search

Let us search for value 40 in the BST above:

BSTSearch(50, 40): 40 < 50 → go left
BSTSearch(30, 40): 40 > 30 → go right
BSTSearch(40, 40): 40 = 40 → Found! Return this node.

Three comparisons. Now search for value 35 (not present):

BSTSearch(50, 35): 35 < 50 → go left
BSTSearch(30, 35): 35 > 30 → go right
BSTSearch(40, 35): 35 < 40 → go left
BSTSearch(nil):    → Not found! Return nil.

Four comparisons to determine that 35 is not in the tree. In a balanced BST of n nodes, this is at most about log2(n) + 1 comparisons.

BST Insert

procedure BSTInsert(var Node: PBTreeNode; Value: Integer);
begin
  if Node = nil then
    Node := NewNode(Value)
  else if Value < Node^.Data then
    BSTInsert(Node^.Left, Value)
  else if Value > Node^.Data then
    BSTInsert(Node^.Right, Value);
  { Equal values are ignored (no duplicates) }
end;

Notice the elegance: the var parameter means the recursive call can modify the pointer directly. When Node is nil, the assignment Node := NewNode(Value) creates the node and links it to the parent — all in one operation, with no special case for the root.

Step-by-Step BST Insertion

Let us build a BST by inserting the values 50, 30, 70, 20, 40, 60, 80 in sequence:

Insert 50: Tree is empty → 50 becomes root.
    50

Insert 30: 30 < 50 → go left. Left is nil → insert here.
    50
   /
  30

Insert 70: 70 > 50 → go right. Right is nil → insert here.
    50
   /  \
  30   70

Insert 20: 20 < 50 → left to 30. 20 < 30 → left is nil → insert.
      50
     /  \
   30    70
   /
  20

Insert 40: 40 < 50 → left to 30. 40 > 30 → right is nil → insert.
      50
     /  \
   30    70
   / \
  20  40

Insert 60: 60 > 50 → right to 70. 60 < 70 → left is nil → insert.
      50
     /  \
   30    70
   / \   /
  20  40 60

Insert 80: 80 > 50 → right to 70. 80 > 70 → right is nil → insert.
      50
     /  \
   30    70
   / \   / \
  20  40 60  80

The resulting tree is perfectly balanced because we happened to insert the median first. If instead we inserted values in sorted order (20, 30, 40, 50, 60, 70, 80), the tree would degenerate into a linked list — a problem addressed in Section 24.4.

BST Delete

Deletion is the most complex BST operation because removing a node must preserve the BST property. There are three cases:

1. Leaf node: Simply remove it (set parent's pointer to nil).
2. Node with one child: Replace the node with its child.
3. Node with two children: Replace the node's value with its in-order successor (the smallest value in its right subtree), then delete the successor.

function FindMin(Node: PBTreeNode): PBTreeNode;
begin
  while Node^.Left <> nil do
    Node := Node^.Left;
  FindMin := Node;
end;

procedure BSTDelete(var Node: PBTreeNode; Value: Integer);
var
  Temp: PBTreeNode;
  Successor: PBTreeNode;
begin
  if Node = nil then Exit;

  if Value < Node^.Data then
    BSTDelete(Node^.Left, Value)
  else if Value > Node^.Data then
    BSTDelete(Node^.Right, Value)
  else begin
    { Found the node to delete }
    if (Node^.Left = nil) and (Node^.Right = nil) then begin
      { Case 1: Leaf }
      Dispose(Node);
      Node := nil;
    end
    else if Node^.Left = nil then begin
      { Case 2a: Only right child }
      Temp := Node;
      Node := Node^.Right;
      Dispose(Temp);
    end
    else if Node^.Right = nil then begin
      { Case 2b: Only left child }
      Temp := Node;
      Node := Node^.Left;
      Dispose(Temp);
    end
    else begin
      { Case 3: Two children }
      Successor := FindMin(Node^.Right);
      Node^.Data := Successor^.Data;
      BSTDelete(Node^.Right, Successor^.Data);
    end;
  end;
end;

Understanding BST Delete: Why Three Cases?

Deletion is tricky because removing a node must not break the BST property. Let us think about each case intuitively:

Case 1 (Leaf): A leaf has no children to worry about. Just remove it. The parent's pointer becomes nil.

Case 2 (One child): If a node has exactly one child, that child can simply take the node's place. The child and all its descendants already satisfy the BST property relative to the deleted node's parent.

Case 3 (Two children): This is the challenging case. We cannot simply remove the node because we would leave two disconnected subtrees. Instead, we find the in-order successor — the smallest value in the right subtree. Why? Because the in-order successor is larger than everything in the left subtree (since it is in the right subtree) and smaller than everything else in the right subtree (since it is the minimum). So it is the perfect replacement: it maintains the BST property for both subtrees. We copy the successor's value into the node being deleted, then recursively delete the successor (which is guaranteed to have at most one child, since it is the minimum of a subtree — it cannot have a left child).

An alternative approach uses the in-order predecessor (the largest value in the left subtree) instead. Both are correct; the choice is a matter of convention.

Step-by-Step BST Deletion

Let us trace the deletion of 30 from our BST (which has two children: 20 and 40):

Starting tree:
      50
     /  \
   30    70
   / \   / \
  20  40 60  80

BSTDelete(root, 30):
  30 < 50 → go left
  BSTDelete(30-node, 30):
    Found! Node has two children.
    Find in-order successor: FindMin(right subtree of 30) = FindMin(40) = 40
    Replace 30's data with 40: node now contains 40
    Delete 40 from right subtree: BSTDelete(40-node, 40)
      Found! 40 is a leaf → Dispose and set to nil.

Result:
      50
     /  \
   40    70
   /    / \
  20   60  80

The BST property is preserved: 20 < 40 < 50, and 60 < 70 < 80.

📊 BST Operation Complexity | Operation | Balanced Tree | Degenerate Tree | |-----------|--------------|----------------| | Search | O(log n) | O(n) | | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) | | In-order | O(n) | O(n) |

24.4 Balanced Trees (AVL Concept, Rotations)

The BST's Achilles heel is degeneration. If you insert values in sorted order (1, 2, 3, 4, 5), the tree degenerates into a linked list:

1
 \
  2
   \
    3
     \
      4
       \
        5

Search on this tree is O(n), not O(log n). We have lost the BST's primary advantage.

Balanced trees solve this by maintaining a height bound. The most famous is the AVL tree (named after Adelson-Velsky and Landis, 1962), which maintains the invariant that for every node, the heights of its left and right subtrees differ by at most 1.

When an insertion or deletion violates this invariant, the tree is rebalanced using rotations — operations that restructure the tree locally without violating the BST ordering property.

Rotations Explained

A right rotation around node X promotes X's left child Y to take X's place:

Before:              After:
    X                  Y
   / \                / \
  Y   C     →       A   X
 / \                    / \
A   B                  B   C

Verify the BST property is preserved: A < Y < B < X < C — this ordering holds in both arrangements. The rotation simply restructures the pointers without changing the relative order of any values.

A left rotation is the mirror image:

Before:              After:
  X                    Y
 / \                  / \
A   Y       →       X   C
   / \              / \
  B   C            A   B

Again, A < X < B < Y < C holds in both arrangements.

When Rotations Are Needed

AVL trees track a balance factor for each node: the height of the left subtree minus the height of the right subtree. When an insertion makes a balance factor +2 or -2, one of four rotation cases applies:

1. Left-Left (LL): The imbalance is caused by an insertion into the left child's left subtree. Fix: single right rotation.
2. Right-Right (RR): Mirror of LL. Fix: single left rotation.
3. Left-Right (LR): Insertion into the left child's right subtree. Fix: left rotation on the child, then right rotation on the node.
4. Right-Left (RL): Mirror of LR. Fix: right rotation on the child, then left rotation on the node.

Example: LL Imbalance and Rotation

Suppose we insert values 30, 20, 10 (in that order) into an AVL tree:

Insert 30:        Insert 20:        Insert 10:
  30                30                30    ← balance factor = 2 (violation!)
                   /                 /
                  20                20
                                   /
                                  10

This is an LL case. Apply right rotation around 30:

    20
   /  \
  10   30

The tree is now balanced: every node's balance factor is 0.

Why We Study AVL Conceptually (Not Fully Implement)

A full AVL tree implementation requires tracking balance factors, detecting imbalances after every insert/delete, and applying the correct rotation (single left, single right, left-right double, right-left double). It is roughly 150-200 lines of careful code. While instructive, the full implementation is typically covered in a dedicated data structures course.

What matters for us is the concept: balanced BSTs guarantee O(log n) operations by preventing degeneration. Free Pascal's standard library provides balanced tree implementations (such as TAVLTree in the AVL_Tree unit) that you should use in production code.

Example: RL Imbalance and Double Rotation

Let us insert 10, 30, 20 into an AVL tree:

Insert 10:        Insert 30:        Insert 20:
  10                10                10    ← balance factor = -2
                      \                 \
                       30                30  ← balance factor = 1
                                        /
                                       20

This is an RL case (right child has left-heavy subtree). First, right-rotate around 30, then left-rotate around 10:

Step 1: Right rotate around 30:    Step 2: Left rotate around 10:
  10                                  20
    \                                /  \
     20                             10   30
      \
       30

Result:
    20
   /  \
  10   30

Now every node has balance factor 0. The double rotation handled the "zigzag" pattern that a single rotation cannot fix.

⚠️ Warning: Unbalanced BSTs Can Be Worse Than Linear Search If you insert sorted data into an unbalanced BST, every operation becomes O(n). This is slower than a sorted array with binary search (which also gives O(log n) search but with better cache locality). Always consider whether your insertion pattern might create a degenerate tree, and use a balanced tree variant if so.

24.5 General Trees and N-ary Trees

Not all trees are binary. A general tree (or N-ary tree) allows each node to have any number of children. We encountered this in Chapter 22 with PennyWise's category tree, where "Food" has three children (Groceries, Restaurants, Coffee) and "Transport" has three (Gas, Public Transit, Rideshare).

Implementation Strategies

Fixed-size child array:

type
  PNaryNode = ^TNaryNode;
  TNaryNode = record
    Data: string[40];
    Children: array[1..10] of PNaryNode;
    ChildCount: Integer;
  end;

Dynamic child list (linked list of children):

type
  PTreeNode = ^TTreeNode;
  TTreeNode = record
    Data: string[40];
    FirstChild: PTreeNode;   { Pointer to first child }
    NextSibling: PTreeNode;  { Pointer to next sibling }
  end;

The "first child, next sibling" representation is memory-efficient and elegant: every N-ary tree can be represented as a binary tree where the left pointer is the first child and the right pointer is the next sibling.

Comparing the Two Representations

Consider PennyWise's category tree with these categories:

All Expenses
├── Food
│   ├── Groceries
│   ├── Restaurants
│   └── Coffee
├── Transport
│   ├── Gas
│   ├── Public Transit
│   └── Rideshare
└── Entertainment

Fixed-size child array: Each node reserves space for 10 children pointers, whether or not they are used. The "All Expenses" node uses 3 of its 10 slots; the leaf nodes (Groceries, Gas, etc.) use 0 of their 10 slots. This wastes memory but makes it easy to add children (just increment ChildCount and set the pointer).

First-child, next-sibling: Each node uses exactly two pointers. "All Expenses" has FirstChild → Food and NextSibling → nil. "Food" has FirstChild → Groceries and NextSibling → Transport. "Groceries" has FirstChild → nil and NextSibling → Restaurants. No wasted space.

The first-child/next-sibling representation is essentially a binary tree in disguise. This is a deep insight: any general tree can be represented as a binary tree using this encoding. The left child of the binary tree is the first child of the original tree; the right child is the next sibling.

Traversing an N-ary Tree

procedure PrintNaryTree(Node: PTreeNode; Indent: Integer);
var
  I: Integer;
  Child: PTreeNode;
begin
  if Node = nil then Exit;

  { Print current node with indentation }
  for I := 1 to Indent do Write('  ');
  WriteLn(Node^.Data);

  { Traverse all children }
  Child := Node^.FirstChild;
  while Child <> nil do begin
    PrintNaryTree(Child, Indent + 1);
    Child := Child^.NextSibling;
  end;
end;

24.6 Graphs: Network Data (Adjacency Matrix, Adjacency List)

Trees impose a strict hierarchy: one parent per node, no cycles. But many real-world relationships are not hierarchical. A road network connects cities in a web — there is no single "root" city. A social network has friendships that go both ways. A dependency graph (which tasks must complete before others) can have multiple paths.

A graph is a collection of vertices (nodes) connected by edges (links). Unlike trees, graphs can have cycles, multiple paths between vertices, and vertices with any number of connections.

Graph Terminology

• Vertex (Node): A point in the graph.
• Edge: A connection between two vertices.
• Directed graph (digraph): Edges have a direction (A -> B does not imply B -> A).
• Undirected graph: Edges go both ways (A -- B means A connects to B and B connects to A).
• Weighted graph: Each edge has a numerical weight (e.g., distance, cost).
• Path: A sequence of vertices connected by edges.
• Cycle: A path that starts and ends at the same vertex.
• Connected: A graph where every vertex can be reached from every other vertex.
• Degree: The number of edges incident to a vertex.

Representation 1: Adjacency Matrix

An adjacency matrix is a 2D array where Matrix[I][J] is 1 if there is an edge from vertex I to vertex J, and 0 otherwise. For weighted graphs, the value is the edge weight instead of 1.

const
  MAX_VERTICES = 20;

type
  TAdjMatrix = array[0..MAX_VERTICES-1, 0..MAX_VERTICES-1] of Integer;
  TGraph = record
    VertexCount: Integer;
    Labels: array[0..MAX_VERTICES-1] of string[20];
    Matrix: TAdjMatrix;
  end;

Building a graph:

procedure InitGraph(var G: TGraph; Count: Integer);
var
  I, J: Integer;
begin
  G.VertexCount := Count;
  for I := 0 to Count - 1 do
    for J := 0 to Count - 1 do
      G.Matrix[I][J] := 0;
end;

procedure AddEdge(var G: TGraph; From, To_: Integer; Weight: Integer);
begin
  G.Matrix[From][To_] := Weight;
  G.Matrix[To_][From] := Weight;  { For undirected graphs }
end;

Pros: O(1) edge lookup. Simple to implement. Cons: O(V^2) space even for sparse graphs. Wastes memory when most entries are 0.

Representation 2: Adjacency List

An adjacency list stores, for each vertex, a list of its neighbors. This is more memory-efficient for sparse graphs (graphs with few edges relative to vertices).

type
  PEdgeNode = ^TEdgeNode;
  TEdgeNode = record
    DestVertex: Integer;
    Weight: Integer;
    Next: PEdgeNode;
  end;

  TAdjList = array[0..MAX_VERTICES-1] of PEdgeNode;
  TGraphList = record
    VertexCount: Integer;
    Labels: array[0..MAX_VERTICES-1] of string[20];
    AdjList: TAdjList;
  end;

Adding an edge to an adjacency list:

procedure AddEdgeList(var G: TGraphList; From, To_: Integer; Weight: Integer);
var
  NewEdge: PEdgeNode;
begin
  New(NewEdge);
  NewEdge^.DestVertex := To_;
  NewEdge^.Weight := Weight;
  NewEdge^.Next := G.AdjList[From];
  G.AdjList[From] := NewEdge;

  { For undirected graphs, add reverse edge too }
  New(NewEdge);
  NewEdge^.DestVertex := From;
  NewEdge^.Weight := Weight;
  NewEdge^.Next := G.AdjList[To_];
  G.AdjList[To_] := NewEdge;
end;

Pros: O(V + E) space. Efficient iteration over neighbors. Cons: O(degree) edge lookup (must scan the neighbor list).

📊 Adjacency Matrix vs. Adjacency List | Operation | Matrix | List | |-----------|--------|------| | Space | O(V^2) | O(V + E) | | Add edge | O(1) | O(1) | | Check edge exists | O(1) | O(degree) | | Iterate neighbors | O(V) | O(degree) | | Best for | Dense graphs | Sparse graphs |

For most practical graphs (road networks, social networks, game maps), the adjacency list is preferred because real-world graphs are usually sparse.

Building a Complete Graph Example

Let us build a small graph representing cities and roads to make these representations concrete.

Cities: A(0), B(1), C(2), D(3), E(4)
Roads: A-B (5 km), A-C (3 km), B-D (2 km), C-D (7 km), C-E (4 km), D-E (1 km)

Adjacency matrix:

     A  B  C  D  E
A  [ 0  5  3  0  0 ]
B  [ 5  0  0  2  0 ]
C  [ 3  0  0  7  4 ]
D  [ 0  2  7  0  1 ]
E  [ 0  0  4  1  0 ]

Space used: 5 * 5 = 25 integers. The matrix is symmetric (undirected graph).

Adjacency list:

A → [B(5), C(3)]
B → [A(5), D(2)]
C → [A(3), D(7), E(4)]
D → [B(2), C(7), E(1)]
E → [C(4), D(1)]

Space used: 5 vertices + 12 edge entries (6 edges, each stored twice for undirected). The adjacency list uses about half the space of the matrix for this sparse graph.

For a social network with 1 million users and an average of 150 friends each, the adjacency matrix would need 10^12 entries (1 terabyte!), while the adjacency list would need only about 150 million entries (manageable). This is why adjacency lists dominate in practice.

24.7 Graph Traversal (BFS, DFS)

The two fundamental graph traversal algorithms visit every vertex reachable from a starting vertex, but in different orders.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion, which uses the call stack implicitly).

procedure DFS(const Graph: TGraph; Start: Integer);
var
  Visited: array[0..MAX_VERTICES-1] of Boolean;

  procedure DFSVisit(V: Integer);
  var
    W: Integer;
  begin
    Visited[V] := True;
    Write(Graph.Labels[V], ' ');

    for W := 0 to Graph.VertexCount - 1 do
      if (Graph.Matrix[V][W] <> 0) and (not Visited[W]) then
        DFSVisit(W);
  end;

var
  I: Integer;
begin
  for I := 0 to Graph.VertexCount - 1 do
    Visited[I] := False;
  DFSVisit(Start);
end;

Breadth-First Search (BFS)

BFS explores all neighbors at the current depth before moving to the next depth level. It uses a queue.

procedure BFS(const Graph: TGraph; Start: Integer);
var
  Visited: array[0..MAX_VERTICES-1] of Boolean;
  Queue: array[0..MAX_VERTICES-1] of Integer;
  Front, Rear: Integer;
  V, W: Integer;
begin
  for V := 0 to Graph.VertexCount - 1 do
    Visited[V] := False;

  { Enqueue start vertex }
  Front := 0;
  Rear := 0;
  Queue[Rear] := Start;
  Inc(Rear);
  Visited[Start] := True;

  while Front < Rear do begin
    V := Queue[Front];
    Inc(Front);
    Write(Graph.Labels[V], ' ');

    for W := 0 to Graph.VertexCount - 1 do
      if (Graph.Matrix[V][W] <> 0) and (not Visited[W]) then begin
        Visited[W] := True;
        Queue[Rear] := W;
        Inc(Rear);
      end;
  end;
end;

Tracing BFS and DFS on a Concrete Graph

Consider this graph (the Crypts of Pascalia dungeon):

    Entrance(0) ---2--- GreatHall(1) ---3--- Armory(2)
                          |                     |
                          4                     5
                          |                     |
                       Library(3) ---2--- Crypt(4)
                          |                     |
                          6                     8
                          |                     |
                      Treasury(5)         DragonLair(6)
                          |                     |
                          3                     1
                          |                     |
                         Exit(7) ------1------ Exit(7)

DFS starting at Entrance (vertex 0):

Visit Entrance(0). Check neighbors: GreatHall(1) is unvisited → recurse.
  Visit GreatHall(1). Neighbors: Entrance(visited), Armory(2), Library(3).
    Visit Armory(2). Neighbors: GreatHall(visited), Crypt(4).
      Visit Crypt(4). Neighbors: Armory(visited), Library(3), DragonLair(6).
        Visit Library(3). Neighbors: GreatHall(visited), Crypt(visited), Treasury(5).
          Visit Treasury(5). Neighbors: Library(visited), Exit(7).
            Visit Exit(7). Neighbors: Treasury(visited), DragonLair(6).
              Visit DragonLair(6). Neighbors: Crypt(visited), Exit(visited).
              Backtrack.
            Backtrack.
          Backtrack.
        Backtrack.
      Backtrack.
    Backtrack.
  Backtrack.

DFS order: Entrance GreatHall Armory Crypt Library Treasury Exit DragonLair

BFS starting at Entrance (vertex 0):

Queue: [Entrance]    Visit: Entrance. Enqueue neighbors: GreatHall.
Queue: [GreatHall]   Visit: GreatHall. Enqueue: Armory, Library.
Queue: [Armory, Library]  Visit: Armory. Enqueue: Crypt.
Queue: [Library, Crypt]   Visit: Library. Enqueue: Treasury.
Queue: [Crypt, Treasury]  Visit: Crypt. Enqueue: DragonLair.
Queue: [Treasury, DragonLair]  Visit: Treasury. Enqueue: Exit.
Queue: [DragonLair, Exit]  Visit: DragonLair. (Exit already queued.)
Queue: [Exit]        Visit: Exit.

BFS order: Entrance GreatHall Armory Library Crypt Treasury DragonLair Exit

Notice the difference: DFS goes deep (Entrance → GreatHall → Armory → Crypt → Library → Treasury → Exit → DragonLair), following one path as far as it goes. BFS spreads outward level by level (1 step from Entrance, then 2 steps, then 3 steps...).

DFS vs. BFS

When to Use DFS vs. BFS

The choice between DFS and BFS depends on the problem you are solving:

Use DFS when: - You need to visit all vertices (traversal order does not matter much). - You are looking for a path (any path, not necessarily the shortest). - You want to detect cycles. - The graph has many branches but limited depth (DFS uses less memory than BFS in this case). - You need a topological ordering of a DAG.

Use BFS when: - You need the shortest path in an unweighted graph (BFS always finds it). - You want to explore vertices in order of distance from the start. - You are doing a level-order traversal of a tree. - The graph is very deep but not very wide (BFS avoids deep recursion).

A practical mnemonic: BFS is for "closest first" problems (shortest path, nearest neighbor). DFS is for "explore everything" problems (reachability, cycle detection, topological sort).

💡 Intuition: DFS vs. BFS as Exploration Strategies Imagine exploring a maze. DFS is like always turning left: you go as deep as you can, then backtrack when you hit a dead end. BFS is like a wave spreading outward from your starting point: you explore all rooms one step away, then two steps, then three. DFS might find the exit faster if it is deep in one branch, but BFS is guaranteed to find the shortest path.

24.8 Shortest Path (Dijkstra's Algorithm)

In a weighted graph, we often want the shortest path — the path between two vertices whose total edge weight is minimal. Edsger Dijkstra's algorithm, published in 1959, solves this problem elegantly.

Idea: Maintain a set of vertices whose shortest distance from the source is known. Initially, only the source is in this set (distance 0). Repeatedly pick the unvisited vertex with the smallest tentative distance, mark it as visited, and update the distances of its unvisited neighbors.

procedure Dijkstra(const Graph: TGraph; Source: Integer;
                   var Dist: array of Integer;
                   var Prev: array of Integer);
var
  Visited: array[0..MAX_VERTICES-1] of Boolean;
  V, U, W: Integer;
  MinDist, NewDist: Integer;
begin
  for V := 0 to Graph.VertexCount - 1 do begin
    Dist[V] := MaxInt;
    Prev[V] := -1;
    Visited[V] := False;
  end;
  Dist[Source] := 0;

  for V := 0 to Graph.VertexCount - 1 do begin
    { Find unvisited vertex with minimum distance }
    U := -1;
    MinDist := MaxInt;
    for W := 0 to Graph.VertexCount - 1 do
      if (not Visited[W]) and (Dist[W] < MinDist) then begin
        MinDist := Dist[W];
        U := W;
      end;

    if U = -1 then Break;  { All remaining vertices unreachable }
    Visited[U] := True;

    { Update distances of neighbors }
    for W := 0 to Graph.VertexCount - 1 do
      if (Graph.Matrix[U][W] > 0) and (not Visited[W]) then begin
        NewDist := Dist[U] + Graph.Matrix[U][W];
        if NewDist < Dist[W] then begin
          Dist[W] := NewDist;
          Prev[W] := U;
        end;
      end;
  end;
end;

Step-by-Step Dijkstra Trace

Let us trace Dijkstra from Entrance (vertex 0) on the dungeon graph:

Initial: Dist = [0, INF, INF, INF, INF, INF, INF, INF]

Iteration 1: Select vertex 0 (Entrance, dist=0)
  Neighbor 1 (GreatHall): 0+2=2 < INF → Dist[1]=2, Prev[1]=0
  Dist = [0, 2, INF, INF, INF, INF, INF, INF]

Iteration 2: Select vertex 1 (GreatHall, dist=2)
  Neighbor 2 (Armory): 2+3=5 < INF → Dist[2]=5, Prev[2]=1
  Neighbor 3 (Library): 2+4=6 < INF → Dist[3]=6, Prev[3]=1
  Dist = [0, 2, 5, 6, INF, INF, INF, INF]

Iteration 3: Select vertex 2 (Armory, dist=5)
  Neighbor 4 (Crypt): 5+5=10 < INF → Dist[4]=10, Prev[4]=2
  Dist = [0, 2, 5, 6, 10, INF, INF, INF]

Iteration 4: Select vertex 3 (Library, dist=6)
  Neighbor 4 (Crypt): 6+2=8 < 10 → Dist[4]=8, Prev[4]=3  ← improvement!
  Neighbor 5 (Treasury): 6+6=12 < INF → Dist[5]=12, Prev[5]=3
  Dist = [0, 2, 5, 6, 8, 12, INF, INF]

Iteration 5: Select vertex 4 (Crypt, dist=8)
  Neighbor 6 (DragonLair): 8+8=16 < INF → Dist[6]=16, Prev[6]=4
  Dist = [0, 2, 5, 6, 8, 12, 16, INF]

Iteration 6: Select vertex 5 (Treasury, dist=12)
  Neighbor 7 (Exit): 12+3=15 < INF → Dist[7]=15, Prev[7]=5
  Dist = [0, 2, 5, 6, 8, 12, 16, 15]

Iteration 7: Select vertex 7 (Exit, dist=15)
  Neighbor 6 (DragonLair): 15+1=16 = 16 → no improvement
  Dist = [0, 2, 5, 6, 8, 12, 16, 15]

Iteration 8: Select vertex 6 (DragonLair, dist=16)
  All neighbors visited.
  Dist = [0, 2, 5, 6, 8, 12, 16, 15]

The shortest path from Entrance to Exit has total weight 15: Entrance(0) -> GreatHall(2) -> Library(6) -> Treasury(12) -> Exit(15).

Time complexity: O(V^2) with the simple implementation above. Using a priority queue (min-heap), this can be improved to O((V + E) log V).

Path Reconstruction

The Prev array enables path reconstruction: to find the shortest path from Source to any vertex T, follow Prev[T] back to Prev[Prev[T]] and so on until you reach Source.

procedure PrintPath(const Graph: TGraph; const Prev: array of Integer;
                    Target: Integer);
begin
  if Prev[Target] <> -1 then begin
    PrintPath(Graph, Prev, Prev[Target]);
    Write(' -> ');
  end;
  Write(Graph.Labels[Target]);
end;

For our example: PrintPath(Graph, Prev, 7) outputs Entrance -> GreatHall -> Library -> Treasury -> Exit.

Cycle Detection with DFS

One important graph application is cycle detection — determining whether a graph contains any cycles. In an undirected graph, DFS finds a cycle when it encounters a visited vertex that is not the parent of the current vertex. In a directed graph, a cycle exists when DFS encounters a vertex that is currently on the recursion stack (a "back edge").

Here is cycle detection for an undirected graph:

function HasCycle(const Graph: TGraph): Boolean;
var
  Visited: array[0..MAX_VERTICES-1] of Boolean;
  Found: Boolean;

  procedure CheckCycle(V, Parent: Integer);
  var
    W: Integer;
  begin
    Visited[V] := True;
    for W := 0 to Graph.VertexCount - 1 do
      if Graph.Matrix[V][W] <> 0 then begin
        if not Visited[W] then
          CheckCycle(W, V)
        else if W <> Parent then
          Found := True;    { Back edge found → cycle! }
      end;
  end;

var
  I: Integer;
begin
  Found := False;
  for I := 0 to Graph.VertexCount - 1 do
    Visited[I] := False;
  CheckCycle(0, -1);
  HasCycle := Found;
end;

In the Crypts of Pascalia dungeon, cycles mean the player can walk in circles — which might be a deliberate design choice (getting lost in a maze) or a bug to detect during dungeon generation.

Topological Sorting (Brief Mention)

For directed acyclic graphs (DAGs), topological sorting produces an ordering of vertices such that every edge goes from an earlier vertex to a later one. This is essential for dependency resolution: if task A must be completed before task B, a topological sort tells you a valid execution order. The algorithm uses DFS: finish a vertex (add it to the front of the result list) only after all its descendants have been finished.

24.9 Crypts of Pascalia Dungeon as a Graph

Crypts of Pascalia's dungeon is a perfect graph application. Each room is a vertex. Each corridor connecting two rooms is an edge. The corridor's length or danger level is the edge weight.

{ Define the dungeon as a weighted graph }
procedure BuildDungeon(var Dungeon: TGraph);
begin
  Dungeon.VertexCount := 8;
  Dungeon.Labels[0] := 'Entrance';
  Dungeon.Labels[1] := 'Great Hall';
  Dungeon.Labels[2] := 'Armory';
  Dungeon.Labels[3] := 'Library';
  Dungeon.Labels[4] := 'Crypt';
  Dungeon.Labels[5] := 'Treasury';
  Dungeon.Labels[6] := 'Dragon Lair';
  Dungeon.Labels[7] := 'Exit';

  { Initialize all edges to 0 }
  FillChar(Dungeon.Matrix, SizeOf(Dungeon.Matrix), 0);

  { Add corridors with danger levels as weights }
  Dungeon.Matrix[0][1] := 2;  Dungeon.Matrix[1][0] := 2;
  Dungeon.Matrix[1][2] := 3;  Dungeon.Matrix[2][1] := 3;
  Dungeon.Matrix[1][3] := 4;  Dungeon.Matrix[3][1] := 4;
  Dungeon.Matrix[2][4] := 5;  Dungeon.Matrix[4][2] := 5;
  Dungeon.Matrix[3][4] := 2;  Dungeon.Matrix[4][3] := 2;
  Dungeon.Matrix[3][5] := 6;  Dungeon.Matrix[5][3] := 6;
  Dungeon.Matrix[4][6] := 8;  Dungeon.Matrix[6][4] := 8;
  Dungeon.Matrix[5][7] := 3;  Dungeon.Matrix[7][5] := 3;
  Dungeon.Matrix[6][7] := 1;  Dungeon.Matrix[7][6] := 1;
end;

With Dijkstra's algorithm, the game can compute the safest path from the player's current room to the exit. With BFS, it can determine the minimum number of rooms to traverse to reach the exit (regardless of danger level). With DFS, it can detect if any cycles exist (rooms that lead back to themselves, creating traps for unwary adventurers).

The game can also offer a hint system: when the player is stuck, compute the shortest path from their current location to the exit and reveal the next room on that path. This requires a single call to Dijkstra followed by a path reconstruction — algorithms we have already implemented.

procedure GiveHint(const Dungeon: TGraph; CurrentRoom: Integer);
var
  Dist: array[0..MAX_VERTICES-1] of Integer;
  Prev: array[0..MAX_VERTICES-1] of Integer;
  NextRoom: Integer;
begin
  Dijkstra(Dungeon, CurrentRoom, Dist, Prev);

  if Dist[7] = MaxInt then   { 7 = Exit }
    WriteLn('There is no path to the exit from here!')
  else begin
    { Find the first room on the shortest path }
    NextRoom := 7;
    while Prev[NextRoom] <> CurrentRoom do
      NextRoom := Prev[NextRoom];
    WriteLn('Hint: try heading toward ', Dungeon.Labels[NextRoom],
            ' (danger level: ', Dungeon.Matrix[CurrentRoom][NextRoom], ')');
  end;
end;

This is Wirth's equation made visible: the data structure (a weighted graph) combined with the algorithm (Dijkstra) produces a program (pathfinding in a dungeon). Neither the data structure nor the algorithm is useful alone; together, they create gameplay.

24.10 Applications Summary: Trees and Graphs in the Real World

Before we move to the project checkpoint, let us step back and see the broader landscape of where trees and graphs appear in real software.

Trees in Practice

Database indexes use B-trees (a generalization of BSTs optimized for disk access) to enable O(log n) lookups in databases with millions of records. When you query SELECT * FROM expenses WHERE amount = 42.50, the database uses a B-tree index to find the matching rows without scanning the entire table.

Compilers use abstract syntax trees (ASTs) to represent the structure of source code. The expression parser from Chapter 22 is a simplified version of what every compiler does. After parsing, the compiler traverses the AST to type-check, optimize, and generate machine code.

File systems are trees: directories contain subdirectories and files. The ls -R command (or dir /s on Windows) performs a pre-order traversal of the file system tree.

Decision trees in machine learning classify data by asking a series of yes/no questions, following different branches based on the answers. The resulting structure is a binary tree where each internal node is a question and each leaf is a classification.

Graphs in Practice

Social networks are graphs where users are vertices and friendships are edges. "People you may know" features use BFS to find users within 2-3 hops of your network.

GPS navigation uses weighted graphs where intersections are vertices, roads are edges, and edge weights are travel times. Dijkstra's algorithm (or its variant A*) finds the shortest route.

The internet is a graph of routers connected by links. Routing protocols (like OSPF) use shortest-path algorithms to determine how to forward packets.

Dependency management in software (npm, pip, cargo) uses directed graphs to track which packages depend on which others. Topological sort determines a valid installation order.

Game AI uses graph search extensively. Pathfinding in strategy games, decision trees in NPC behavior, and state-space search in puzzle games all rely on the algorithms we studied in this chapter.

24.11 Project Checkpoint: PennyWise Category Tree and Expense Graph

PennyWise now combines two of this chapter's data structures:

Category Tree (BST)

Rosa's categories are stored in a BST for efficient alphabetical lookup:

type
  PCatBSTNode = ^TCatBSTNode;
  TCatBSTNode = record
    Name: string[40];
    TotalSpent: Currency;
    Left, Right: PCatBSTNode;
  end;

Inserting, searching, and listing categories alphabetically all benefit from the BST structure. In-order traversal produces an alphabetized category list. Search by category name is O(log n) on a balanced tree.

Expense Relationship Graph

Tomas notices that certain expense categories tend to co-occur: when he spends on "Restaurants," he often also spends on "Rideshare" the same evening. PennyWise models this as a graph where vertices are categories and edge weights represent how often two categories appear together in the same time window.

This co-occurrence graph enables insights like: - "When you spend on Coffee, you usually also spend on Food within the same day." - "Transport and Entertainment are strongly correlated on weekends."

Dijkstra's algorithm is not the right tool here (it finds shortest paths), but BFS and DFS can identify connected components — groups of categories that tend to co-occur — which help Rosa understand her spending patterns.

Complete PennyWise Category Operations

Let us see how the category BST integrates with the expense system. When Rosa adds an expense, the system updates the category tree:

procedure AddExpenseToCategory(var Root: PCatBSTNode;
                                const CatName: string;
                                Amount: Currency);
var
  Node: PCatBSTNode;
begin
  { Search for the category }
  Node := Root;
  while Node <> nil do begin
    if CatName = Node^.Name then begin
      Node^.TotalSpent := Node^.TotalSpent + Amount;
      Exit;
    end
    else if CatName < Node^.Name then
      Node := Node^.Left
    else
      Node := Node^.Right;
  end;
  { Category not found — add it }
  CatBSTInsert(Root, CatName, Amount);
end;

When Rosa wants a report, in-order traversal produces categories in alphabetical order:

procedure PrintCategoryReport(Node: PCatBSTNode);
begin
  if Node = nil then Exit;
  PrintCategoryReport(Node^.Left);
  WriteLn(Node^.Name:20, ': $', Node^.TotalSpent:8:2);
  PrintCategoryReport(Node^.Right);
end;

Sample output:

          Coffee: $  113.00
     Entertainment: $  156.00
            Food: $  823.00
             Gas: $  280.00
       Groceries: $  412.00
        Internet: $  200.00
   Public Transit: $   95.50
     Restaurants: $  298.00
       Rideshare: $   70.00
       Utilities: $  423.00

The BST gives O(log n) category lookup (when balanced) compared to O(n) for linear search through an unsorted list. For a user with 50 expense categories, that is roughly 6 comparisons per expense vs. 25 — not a dramatic difference for 50 categories, but the principle scales. A financial application with 10,000 expense codes would see a meaningful performance difference.

🔗 Cross-Reference: In Chapter 25, we will use dynamic programming on the category tree to optimize Rosa's budget allocation, and in Chapter 26, we will analyze the time complexity of all these tree and graph operations.

24.12 Summary

This chapter introduced the two most general and powerful data structures in computer science: trees and graphs.

Trees represent hierarchical relationships. A binary tree has at most two children per node. A binary search tree (BST) maintains an ordering property that enables O(log n) search, insert, and delete — provided the tree remains balanced. The three tree traversals — in-order, pre-order, and post-order — each serve different purposes and all benefit from recursion's natural fit with tree structures. We traced each traversal in detail and added level-order traversal using a queue.

BST operations — search, insert, and delete — were implemented with full step-by-step traces showing how the tree evolves. The delete operation has three cases (leaf, one child, two children) and uses the in-order successor for the two-child case.

Balanced trees (such as AVL trees) prevent the BST from degenerating into a linked list by maintaining a height constraint through rotations. We examined single rotations and the four imbalance cases (LL, RR, LR, RL). In production code, always use a balanced tree variant when insertion order might be sorted.

General trees and N-ary trees allow any number of children per node and model real-world hierarchies like file systems and organizational charts. The "first child, next sibling" representation converts any N-ary tree to a binary tree.

Graphs represent arbitrary connections between entities. The two standard representations are the adjacency matrix (O(V^2) space, O(1) edge lookup) and the adjacency list (O(V + E) space, efficient neighbor iteration). Most real-world graphs are sparse, making adjacency lists the preferred representation.

DFS explores deeply before backtracking (uses a stack). BFS explores breadth-first (uses a queue) and finds shortest paths in unweighted graphs. Dijkstra's algorithm finds shortest paths in weighted graphs with non-negative edge weights. We traced all three algorithms on the Crypts of Pascalia dungeon graph, step by step.

The Crypts of Pascalia dungeon map and PennyWise's category-and-expense system both demonstrate that choosing the right data structure is half the battle. The algorithms that operate on these structures — traversal, search, shortest path — provide the other half.

📊 Key Concepts at a Glance | Concept | Definition | |---------|-----------| | Binary tree | Tree with at most 2 children per node | | BST | Binary tree where left < node < right | | In-order traversal | Left, Visit, Right — produces sorted order for BST | | Pre-order traversal | Visit, Left, Right — copies tree structure | | Post-order traversal | Left, Right, Visit — processes children first | | Level-order traversal | BFS on a tree — visits level by level | | AVL tree | Self-balancing BST (heights differ by at most 1) | | Rotation | Local restructuring to restore balance | | Graph | Vertices connected by edges; may have cycles | | Adjacency matrix | 2D array representation; O(V^2) space | | Adjacency list | Linked lists of neighbors; O(V+E) space | | DFS | Stack-based deep exploration | | BFS | Queue-based level-order exploration | | Dijkstra's algorithm | Shortest path in weighted graphs; O(V^2) |

Next: Chapter 25 — Algorithm Design Strategies: Divide and Conquer, Greedy, Dynamic Programming