Graph vs Tree Key Structural Difference in DSA Rust - Key Differences

Recall & Review

beginner

What is the main structural difference between a graph and a tree?

A tree is a special type of graph that has no cycles and exactly one path between any two nodes, while a graph can have cycles and multiple paths between nodes.

beginner

Can a tree have cycles? Why or why not?

No, a tree cannot have cycles because it must have exactly one path between any two nodes, ensuring no loops exist.

beginner

Is it possible for a graph to be disconnected? Explain.

Yes, a graph can be disconnected, meaning some nodes are not reachable from others. A tree, however, is always connected.

beginner

What does it mean for a tree to be 'rooted'?

A rooted tree has one special node called the root, from which all other nodes descend. This gives a clear parent-child hierarchy.

beginner

How do edges differ in a tree compared to a general graph?

In a tree with n nodes, there are exactly n-1 edges with no cycles, while a graph can have any number of edges and may contain cycles.

Which of the following is true about trees?

A They have no cycles and are connected.

B They can have cycles and be disconnected.

C They always have multiple paths between nodes.

D They have more edges than nodes.

Trees have no cycles and are always connected with exactly one path between any two nodes.

What is a key difference between a graph and a tree?

A Graphs cannot have cycles, trees can.

B Trees have exactly one path between nodes, graphs may have multiple.

C Graphs always have fewer edges than nodes.

D Trees can be disconnected.

Trees have exactly one path between any two nodes, while graphs can have multiple paths and cycles.

Can a graph be disconnected?

A Only trees can be disconnected.

B No, graphs are always connected.

C Yes, graphs can be disconnected.

D Graphs must have cycles to be disconnected.

Graphs can be disconnected, meaning some nodes cannot be reached from others.

How many edges does a tree with 5 nodes have?

A 4

B 5

C 6

D 3

A tree with n nodes always has n-1 edges, so 5 nodes have 4 edges.

What is a 'root' in a tree?

A A node that forms a cycle.

B A node with no children.

C A node connected to all other nodes.

D A special node from which all others descend.

The root is the starting node of a tree, from which all other nodes descend.

Explain the key structural differences between a graph and a tree.

Think about cycles, connectivity, and number of edges.

Describe why a tree is considered a special type of graph.

Focus on paths and cycles.

Practice

1. Which of the following is a key structural difference between a graph and a tree?

easy

A. A tree has no cycles, but a graph can have cycles.

B. A graph always has a root node, but a tree does not.

C. A tree can have multiple edges between the same nodes, but a graph cannot.

D. A graph is always directed, but a tree is always undirected.

Solution

1. Step 1: Understand cycle presence in trees and graphs

   Trees are acyclic by definition, meaning they do not contain any cycles. Graphs can have cycles or be acyclic.

2. Step 2: Analyze other options for correctness

   Graphs do not always have a root node; trees do have a root. Multiple edges can exist in graphs (multigraphs), but trees do not have multiple edges between the same nodes. Both graphs and trees can be directed or undirected.

3. Final Answer:

   A tree has no cycles, but a graph can have cycles. -> Option A

4. Quick Check:

   Cycle presence = Tree no, Graph yes [OK]

Hint: Trees never have cycles; graphs can have cycles [OK]

Common Mistakes:

• Thinking graphs always have a root node
• Believing trees can have cycles
• Confusing directionality rules

2. Which Rust code snippet correctly declares a tree node struct with a parent and children?

easy

A. struct TreeNode { parent: Option<TreeNode>, children: Vec }

B. struct TreeNode { parent: TreeNode, children: Vec<TreeNode> }

C. struct TreeNode { parent: Box<TreeNode>, children: Vec<TreeNode> }

D. struct TreeNode { parent: Option, children: Vec }

Solution

1. Step 1: Understand ownership and optional parent in Rust

   Parent can be None (root node), so Option is needed. Box is used for heap allocation to avoid recursive size issues.

2. Step 2: Check children vector type

   Children are multiple nodes, so Vec is correct to hold multiple heap-allocated nodes.

3. Final Answer:

   struct TreeNode { parent: Option, children: Vec } -> Option D

4. Quick Check:

   Use Option and Box for recursive tree nodes [OK]

Hint: Use Option for optional recursive fields in Rust [OK]

Common Mistakes:

• Using direct TreeNode type causing infinite size error
• Not using Option for nullable parent
• Using Vec<TreeNode> without Box causing stack overflow

3. Given the following Rust code representing a graph adjacency list, what is the output of printing the neighbors of node 1?

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

medium

A. [0, 3]

B. [1, 2]

C. [1, 3]

D. [0, 1]

Solution

1. Step 1: Identify neighbors of node 1 in adjacency list

   graph[1] is the second element: vec![0, 3], meaning node 1 connects to nodes 0 and 3.

2. Step 2: Confirm printed output matches neighbors

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

3. Final Answer:

   [0, 3] -> Option A

4. Quick Check:

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

Hint: Index adjacency list by node number to get neighbors [OK]

Common Mistakes:

• Confusing node indices and neighbors
• Printing wrong vector index
• Misreading vector contents

4. Consider this Rust code snippet for a tree structure:

struct Node {
    value: i32,
    children: Vec<Node>,
}

fn add_child(parent: &mut Node, child: Node) {
    parent.children.push(child);
}

fn main() {
    let mut root = Node { value: 1, children: vec![] };
    let child = Node { value: 2, children: vec![] };
    add_child(&mut root, child);
    println!("{}", root.children[0].value);
}

What error will this code produce?

medium

A. Compilation error due to recursive struct size

B. Compilation error due to borrowing rules

C. No error; prints 2

D. Runtime panic due to index out of bounds

Solution

1. Step 1: Analyze struct and function usage

   Node struct holds children as Vec<Node>, which is allowed because Vec is heap allocated. add_child pushes child correctly.

2. Step 2: Check main function behavior

   Root node is mutable, child is created and added. Printing root.children[0].value prints 2 without error.

3. Final Answer:

   No error; prints 2 -> Option C

4. Quick Check:

   Vec<Node> allows recursive tree; code runs fine [OK]

Hint: Vec stores heap data; recursive structs allowed [OK]

Common Mistakes:

• Expecting recursive struct size error without Box
• Confusing borrowing errors
• Assuming runtime panic on valid index

5. You want to represent a directed acyclic graph (DAG) in Rust and ensure it has no cycles. Which approach best enforces the key structural difference from a tree?

hard

A. Use a tree struct with parent pointers and children vectors, disallowing cycles by design.

B. Use a graph adjacency list with cycle detection logic during edge insertion.

C. Use a graph with multiple edges allowed and no cycle checks.

D. Use a tree struct but allow cycles by linking nodes arbitrarily.

Solution

1. Step 1: Understand DAG vs Tree structure

   DAGs allow multiple parents but no cycles. Trees have exactly one parent per node except root.

2. Step 2: Evaluate approaches for cycle prevention

   Using adjacency list with cycle detection on edge insertion ensures no cycles, fitting DAG definition. Trees disallow multiple parents, so not suitable for DAGs.

3. Final Answer:

   Use a graph adjacency list with cycle detection logic during edge insertion. -> Option B

4. Quick Check:

   DAG = graph + cycle check [OK]

Hint: Detect cycles on insert to keep DAG acyclic [OK]

Common Mistakes:

• Confusing trees with DAGs
• Ignoring cycle detection in graphs
• Allowing cycles in supposed DAG