Chapter 24 Exercises: Trees and Graphs
Part A: Conceptual Understanding
A.1. Define the following terms and give an example of each: root, leaf, internal node, height, depth, subtree. Use a diagram.
Guidance
Draw a tree with at least 7 nodes. Root: the top node (depth 0). Leaf: a node with no children. Internal node: a node with at least one child. Height: longest path from a node to a leaf. Depth: number of edges from root to that node. Subtree: a node and all its descendants.A.2. Given the BST below, show the result of in-order, pre-order, and post-order traversals.
25
/ \
15 35
/ \ / \
10 20 30 40
Guidance
In-order: 10 15 20 25 30 35 40 (sorted!). Pre-order: 25 15 10 20 35 30 40. Post-order: 10 20 15 30 40 35 25.A.3. Insert the values 50, 30, 70, 20, 40, 60, 80, 10, 25 into an empty BST (in that order). Draw the resulting tree. What is its height?
Guidance
50 is root. 30 goes left, 70 goes right. 20 goes left of 30, 40 goes right of 30. 60 goes left of 70, 80 goes right of 70. 10 goes left of 20, 25 goes right of 20. Height = 3 (path: 50→30→20→10).A.4. Insert the same values from A.3 in sorted order: 10, 20, 25, 30, 40, 50, 60, 70, 80. Draw the resulting tree. What is its height? Why is this a problem?
Guidance
The tree degenerates into a right-leaning linked list. Height = 8 (one less than the number of nodes). Every operation becomes O(n) instead of O(log n). This demonstrates why balanced trees are important.A.5. Explain the difference between DFS and BFS. For the following graph, show the order of vertices visited by each algorithm starting from vertex A.
A -- B -- E
| | |
C -- D -- F
Guidance
DFS (starting from A, choosing alphabetical order for ties): A, B, D, C, E, F. BFS: A, B, C, D, E, F (by levels: level 0: A; level 1: B, C; level 2: D, E; level 3: F — exact order depends on neighbor ordering).A.6. Why does BFS find the shortest path in an unweighted graph but DFS does not? Give an example.
Guidance
BFS explores vertices in order of increasing distance from the source. The first time BFS reaches a vertex, it has found the shortest path. DFS may reach a vertex via a long detour before finding a short path. Example: graph A-B, A-C, C-B. DFS from A might visit A→C→B (distance 2) while the direct path A→B has distance 1.A.7. Explain Dijkstra's algorithm in your own words. Why does it not work with negative edge weights?
Guidance
Dijkstra maintains tentative distances and greedily picks the unvisited vertex with the smallest distance. It assumes that once a vertex is "visited," its shortest distance is final. Negative edges violate this assumption: a later discovery of a negative edge could reduce an already-finalized distance, leading to incorrect results.Part B: Applied Analysis
B.1. Rosa's PennyWise has 50 expense categories. She stores them in a BST. If the categories are inserted in alphabetical order, what happens to performance? Propose a solution.
Guidance
Alphabetical insertion creates a degenerate BST (linked list). All operations become O(n) instead of O(log n). Solution: use a balanced tree (AVL or red-black) that performs rotations after insertions, or insert categories in random order, or build the tree from a sorted array using the middle-element-as-root technique.B.2. The Crypts of Pascalia dungeon has 100 rooms with an average of 3 corridors per room. Should the game use an adjacency matrix or adjacency list? Calculate the memory usage of each.
Guidance
Adjacency matrix: 100 × 100 × 4 bytes = 40,000 bytes, mostly zeros. Adjacency list: 100 vertex headers + 300 edge nodes ≈ 100 × 8 + 300 × 12 = 4,400 bytes. The adjacency list uses about 9x less memory. For a sparse graph (300 edges out of a possible 9,900), adjacency list is strongly preferred.B.3. Tomás wants PennyWise to find the "most connected" expense category — the category that co-occurs with the most other categories. Which graph algorithm or metric would you use?
Guidance
Compute the degree of each vertex in the co-occurrence graph (the number of edges connected to it). The vertex with the highest degree is the most connected category. This requires a single pass through the adjacency list: O(V + E). No complex algorithm needed.Part C: Code Exercises
C.1. Write a function TreeSize(Node: PBTreeNode): Integer that counts the total number of nodes in a binary tree.
Hint
Base case: nil returns 0. Recursive case: 1 + TreeSize(Left) + TreeSize(Right).C.2. Write a function TreeHeight(Node: PBTreeNode): Integer that returns the height of a binary tree.
Hint
Base case: nil returns -1 (or 0, depending on convention). Recursive case: 1 + Max(TreeHeight(Left), TreeHeight(Right)).C.3. Write a function IsValidBST(Node: PBTreeNode; Min, Max: Integer): Boolean that checks whether a binary tree satisfies the BST property.
Hint
Every node's value must be between Min and Max (exclusive). For the left subtree, Max becomes the parent's value. For the right subtree, Min becomes the parent's value. Initially call with Min = Low(Integer) and Max = High(Integer).C.4. Write a procedure LevelOrder(Root: PBTreeNode) that performs a level-order (BFS) traversal of a binary tree, printing each level on a separate line.
Hint
Use a queue. After dequeuing a node, enqueue its children. To separate levels, either track the number of nodes at each level or use a sentinel value in the queue.C.5. Implement a graph using an adjacency list representation. Write AddEdge, RemoveEdge, HasEdge, PrintGraph, DFS, and BFS procedures.
Hint
Each vertex has a linked list of neighbors. AddEdge creates a new node and prepends it to the appropriate list. For undirected graphs, add edges in both directions.C.6. Implement Dijkstra's algorithm for an adjacency-list graph representation. Test it on the Crypts of Pascalia dungeon map from Section 24.9.
Hint
The main difference from the matrix version is iterating neighbors: instead of scanning all V vertices, iterate only the neighbor list of the current vertex.C.7. Write a function FindPath(Graph, Start, End): string that uses BFS to find the shortest path (fewest edges) between two vertices in an unweighted graph. Return the path as a string of vertex labels.
Hint
BFS naturally finds shortest paths. Maintain a Prev array (like in Dijkstra) to reconstruct the path. After BFS completes, follow Prev from End back to Start.Part D: Challenge Exercises
D.1. BST to Sorted Array. Write a procedure that converts a BST to a sorted array using in-order traversal. Then write the reverse: a function that builds a balanced BST from a sorted array.
Hint
For the reverse: use the middle element as root, recursively build left subtree from the left half and right subtree from the right half. This produces a perfectly balanced BST.D.2. Cycle Detection. Write a function that detects whether a directed graph contains a cycle. Use DFS with three-color marking (white/gray/black).
Hint
White = unvisited, Gray = currently being explored, Black = fully explored. If DFS encounters a gray vertex, there is a cycle (a back edge). This is the standard cycle detection algorithm.D.3. Topological Sort. Implement topological sort for a directed acyclic graph (DAG). Apply it to a course prerequisite graph where each vertex is a course and edges represent "must take before" relationships.
Hint
Run DFS. When a vertex finishes (all descendants explored), push it onto a stack. The stack order is a valid topological sort. Alternatively, repeatedly find vertices with no incoming edges (Kahn's algorithm).D.4. Expression Tree. Build an expression tree from a postfix expression like "3 4 + 2 *". Implement evaluation by post-order traversal. Implement display by in-order traversal (with parentheses).
Hint
Parse left to right. When you encounter a number, create a leaf node and push it onto a stack. When you encounter an operator, pop two nodes, create an operator node with them as children, and push the result. The final stack element is the root.D.5. PennyWise Graph Analysis. Build a co-occurrence graph from PennyWise expense data. Two categories are connected if they appear on the same day. Weight = number of co-occurrences. Find the most connected category, identify clusters using connected components, and find the strongest co-occurrence pair.
Hint
For each day, find all categories with expenses. Add edges between every pair. Connected components can be found with BFS or DFS. The strongest pair is the edge with the highest weight.Part M: Interleaving Review (Spaced Practice)
M.1. (From Ch 14/15) How does a BST node's structure relate to a linked list node? What is the key difference?
Guidance
A linked list node has one pointer (Next). A BST node has two pointers (Left, Right). Both use dynamic allocation with New/Dispose. The key difference: a linked list is linear (each node leads to one next node), while a BST branches (each node leads to two possible paths). This branching is what gives BSTs their O(log n) search — each comparison eliminates half the tree.M.2. (From Ch 22) Why are recursive algorithms natural for trees? What would an iterative in-order traversal look like?
Guidance
Trees are recursively defined (a tree is a node plus subtrees), so recursive algorithms mirror the structure perfectly. Iterative in-order traversal requires an explicit stack: push nodes while going left, pop when hitting nil, visit the popped node, then go right. It is about 3x more code and harder to understand.M.3. (From Ch 23) Binary search on a sorted array and BST search are conceptually similar. Compare them. When would you prefer each?
Guidance
Both eliminate half the remaining elements per comparison: O(log n). Binary search on arrays has better cache locality (contiguous memory) and requires no pointers. BSTs support dynamic insertion/deletion without shifting elements. Prefer arrays for static data with frequent searches; prefer BSTs when data changes frequently.M.4. (From Ch 9) An adjacency matrix is a 2D array. If a graph has 1000 vertices, how much memory does the matrix use (assuming 4-byte integers)? Is this acceptable?