Why Graphs Exist and What Trees Cannot Model in DSA Rust - Why This Pattern

Mental Model

Trees show connections like family trees, but graphs let things connect in many ways, even loops and shared links.

Analogy: Think of a tree as a family tree where each person has one parent, but a graph is like a city map where roads connect many places in many ways, including loops and shortcuts.

Tree:
  1
 / \
2   3

Graph:
1 -> 2
↑ ↘
4 ← 3

Dry Run Walkthrough

Input: Tree with nodes 1, 2, 3; Graph with nodes 1, 2, 3, 4 and edges 1->2, 2->3, 3->4, 4->1 (loop)

Goal: Show that trees cannot represent loops or multiple connections between nodes, but graphs can.

Step 1: Draw a tree with root 1 and children 2 and 3

1 -> 2
  -> 3
null

Why: Trees have one parent per node and no loops

Step 2: Try to add an edge from 3 back to 1 in the tree

1 -> 2
  -> 3
3 -> 1 (invalid in tree)

Why: Trees cannot have cycles or loops

Step 3: Draw a graph with nodes 1, 2, 3, 4 and edges 1->2, 2->3, 3->4, 4->1

1 -> 2 -> 3 -> 4 -> 1 (loop)

Why: Graphs allow cycles and multiple connections

Result:

Graph with loop: 1 -> 2 -> 3 -> 4 -> 1
Tree cannot represent this loop

Annotated Code

DSA Rust

use std::collections::HashMap;

struct Graph {
    edges: HashMap<i32, Vec<i32>>,
}

impl Graph {
    fn new() -> Self {
        Graph { edges: HashMap::new() }
    }

    fn add_edge(&mut self, from: i32, to: i32) {
        self.edges.entry(from).or_insert(Vec::new()).push(to);
    }

    fn print_graph(&self) {
        for (node, neighbors) in &self.edges {
            print!("{} -> ", node);
            for n in neighbors {
                print!("{} ", n);
            }
            println!("null");
        }
    }
}

fn main() {
    // Tree example (no cycles)
    println!("Tree structure (no cycles):");
    println!("1 -> 2 null");
    println!("  -> 3 null");

    // Graph example with cycle
    let mut graph = Graph::new();
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);
    graph.add_edge(3, 4);
    graph.add_edge(4, 1); // cycle edge

    println!("\nGraph structure with cycle:");
    graph.print_graph();
}

graph.add_edge(4, 1); // cycle edge

Add edge creating a cycle, which trees cannot have

graph.print_graph();

Print all edges showing graph structure including cycles

Output

Tree structure (no cycles):

1 -> 2 null

  -> 3 null



Graph structure with cycle:

1 -> 2 null

2 -> 3 null

3 -> 4 null

4 -> 1 null

Complexity Analysis

Time: O(E) because printing all edges requires visiting each edge once

Space: O(V + E) because graph stores all vertices and edges

vs Alternative: Trees use less space and simpler structure but cannot represent cycles or multiple parents; graphs handle complex connections at higher cost

Edge Cases

Empty graph

No nodes or edges to show, prints nothing

DSA Rust

for (node, neighbors) in &self.edges {

Single node with no edges

Node exists but no neighbors, prints node with no edges

DSA Rust

self.edges.entry(from).or_insert(Vec::new()).push(to);

When to Use This Pattern

When a problem involves connections that can loop back or have multiple links between points, reach for graph structures because trees cannot model cycles or multiple parents.

Common Mistakes

Mistake: Trying to represent cycles using a tree structure
Fix: Use a graph data structure that allows cycles and multiple edges

Summary

Graphs represent complex connections including loops and multiple links, unlike trees.

Use graphs when relationships are not strictly hierarchical or acyclic.

The key insight is that trees are a special kind of graph without cycles or multiple parents.

Practice

1. Why do we need graphs when we already have trees in data structures?

easy

A. Because graphs can represent connections between nodes that trees cannot, like cycles and multiple parents.

B. Because trees are faster to traverse than graphs.

C. Because trees use less memory than graphs.

D. Because graphs only store numbers, while trees store strings.

Solution

1. Step 1: Understand tree structure limitations

   Trees have a strict hierarchy where each node has only one parent and no cycles.

2. Step 2: Identify graph capabilities

   Graphs allow nodes to have multiple connections, including cycles and multiple parents, which trees cannot model.

3. Final Answer:

   Because graphs can represent connections between nodes that trees cannot, like cycles and multiple parents. -> Option A

4. Quick Check:

   Graphs model cycles and multiple parents [OK]

Hint: Graphs allow cycles and multiple parents; trees do not [OK]

Common Mistakes:

• Thinking trees can have cycles
• Confusing memory use with structure capability
• Assuming graphs only store numbers

2. Which of the following Rust code snippets correctly declares an undirected graph using adjacency lists?

easy

A. let graph: Vec<usize> = vec![0, 1, 2];

B. let graph: Vec = vec![vec![], vec![], vec![]];

C. let graph: HashMap = HashMap::new();

D. let graph: Vec<(usize, usize)> = vec![(0, 1), (1, 2)];

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list is a vector of vectors where each inner vector holds neighbors of a node.

2. Step 2: Match code to adjacency list

   let graph: Vec = vec![vec![], vec![], vec![]]; declares a vector of vectors of usize, suitable for adjacency lists.

3. Final Answer:

   let graph: Vec = vec![vec![], vec![], vec![]]; -> Option B

4. Quick Check:

   Adjacency list = Vec [OK]

Hint: Adjacency list uses Vec of Vec for neighbors [OK]

Common Mistakes:

• Using Vec<usize> instead of Vec
• Using HashMap with wrong types
• Using edge list instead of adjacency list

3. Consider this Rust code that builds a graph and prints neighbors of node 1:

let mut graph = vec![vec![], vec![], vec![]];
graph[0].push(1);
graph[1].push(0);
graph[1].push(2);
graph[2].push(1);
println!("{:?}", graph[1]);

What is the output?

medium

A. [2]

B. [1, 2]

C. [0, 1]

D. [0, 2]

Solution

1. Step 1: Trace graph construction

   graph[1] has neighbors pushed: 0 and 2, so graph[1] = [0, 2].

2. Step 2: Print neighbors of node 1

   Printing graph[1] outputs [0, 2].

3. Final Answer:

   [0, 2] -> Option D

4. Quick Check:

   Neighbors of node 1 = [0, 2] [OK]

Hint: Check which neighbors were pushed to node 1's list [OK]

Common Mistakes:

• Confusing node indices
• Assuming neighbors include the node itself
• Mixing order of neighbors

4. This Rust code tries to add an edge to a graph but causes a runtime error:

let mut graph = vec![vec![], vec![]];
graph[0].push(1);
graph[1].push(0);
graph[2].push(1);

What is the error and how to fix it?

medium

A. Index out of bounds error; fix by increasing graph size to include index 2.

B. Type mismatch error; fix by changing Vec to HashMap.

C. Syntax error; fix by adding semicolons.

D. Logic error; fix by removing graph[1].push(0).

Solution

1. Step 1: Identify cause of runtime error

   graph has length 2, so graph[2] access is out of bounds causing panic.

2. Step 2: Fix by resizing graph

   Increase graph size to at least 3 elements to allow graph[2].push(1).

3. Final Answer:

   Index out of bounds error; fix by increasing graph size to include index 2. -> Option A

4. Quick Check:

   Accessing graph[2] with size 2 causes error [OK]

Hint: Check vector size before indexing [OK]

Common Mistakes:

• Ignoring vector size limits
• Confusing syntax and runtime errors
• Removing unrelated lines

5. You want to model a social network where users can be friends with multiple people and friendships can be mutual or one-way. Why is a graph a better choice than a tree for this model?

hard

A. Because trees can only store numbers, not user data.

B. Because trees are faster to search in social networks.

C. Because graphs allow cycles and multiple connections, representing mutual and one-way friendships.

D. Because graphs use less memory than trees.

Solution

1. Step 1: Understand social network connections

   Users can have multiple friends, and friendships can be mutual (cycles) or one-way (directed edges).

2. Step 2: Compare tree and graph capabilities

   Trees cannot represent cycles or multiple parents, but graphs can model these complex relationships.

3. Step 3: Conclude best data structure

   Graphs are better because they allow cycles and multiple connections needed for social networks.

4. Final Answer:

   Because graphs allow cycles and multiple connections, representing mutual and one-way friendships. -> Option C

5. Quick Check:

   Social network needs cycles and multiple edges [OK]

Hint: Social networks need cycles and multiple edges; use graphs [OK]

Common Mistakes:

• Thinking trees can model mutual friendships
• Confusing data type storage with structure capability
• Assuming trees use less memory always