Graph vs Tree Key Structural Difference in DSA Rust - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

Key Structural Difference Between Graph and Tree

Which statement correctly describes the key structural difference between a graph and a tree?

A A tree is a connected graph with no cycles, while a graph can have cycles and may be disconnected.

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

C A tree can have cycles, but a graph cannot have cycles.

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

💡 Hint

Think about connectivity and cycles in both structures.

A tree is a special type of graph that is connected and has no cycles. Graphs can be disconnected and may contain cycles.

❓ Predict Output

intermediate

Output of Rust Code Representing Graph and Tree Edges

What is the printed output of this Rust code that builds edges for a tree and a graph?

DSA Rust

fn main() {
    let tree_edges = vec![(1, 2), (1, 3), (3, 4)];
    let graph_edges = vec![(1, 2), (2, 3), (3, 1), (4, 5)];
    println!("Tree edges: {:?}", tree_edges);
    println!("Graph edges: {:?}", graph_edges);
}

A Tree edges: [(1, 2), (1, 3), (3, 4)]\nGraph edges: [(1, 2), (2, 3), (3, 1), (4, 5)]

B Tree edges: [(1, 2), (1, 3), (3, 4)]\nGraph edges: [(1, 2), (2, 3), (4, 5)]

C Tree edges: [(1, 2), (1, 3)]\nGraph edges: [(1, 2), (2, 3), (3, 1), (4, 5)]

D Tree edges: [(1, 2), (1, 3), (3, 4)]\nGraph edges: [(1, 2), (3, 1), (4, 5)]

💡 Hint

Look carefully at the vectors defined for edges.

The code prints exactly the vectors defined for tree_edges and graph_edges without modification.

🔧 Debug

advanced

Identify the Error in Tree Construction Code

What error will this Rust code produce when trying to build a tree adjacency list?

DSA Rust

use std::collections::HashMap;

fn main() {
    let edges = vec![(1, 2), (1, 3), (3, 4)];
    let mut adj_list: HashMap<i32, Vec<i32>> = HashMap::new();
    for (u, v) in edges {
        adj_list.entry(u).or_insert(vec![]).push(v);
        adj_list.entry(v).or_insert(vec![]).push(u);
    }
    println!("Adjacency list: {:?}", adj_list);
}

A TypeError because vec![] is not mutable.

B SyntaxError due to missing semicolon after for loop.

C No error; code runs and prints adjacency list correctly.

D Runtime panic due to key not found in HashMap.

💡 Hint

Check if the code uses correct methods to insert and push values.

The code correctly builds an undirected adjacency list by inserting and pushing neighbors. It runs without errors.

🚀 Application

advanced

Detecting Cycle in a Graph Using DFS

Which Rust function correctly detects a cycle in an undirected graph using DFS?

DSA Rust

fn has_cycle(node: usize, parent: usize, visited: &mut Vec<bool>, adj: &Vec<Vec<usize>>) -> bool {
    visited[node] = true;
    for &neighbor in &adj[node] {
        if !visited[neighbor] {
            if has_cycle(neighbor, node, visited, adj) {
                return true;
            }
        } else if neighbor != parent {
            return true;
        }
    }
    false
}

A The function incorrectly treats parent as a cycle causing false positives.

B The function returns true if a cycle is found; otherwise false. It correctly checks neighbors except the parent.

C The function returns true only if all nodes are visited, ignoring cycles.

D The function never marks nodes as visited, causing infinite recursion.

💡 Hint

Focus on how the function handles visited nodes and parent node.

This DFS function correctly detects cycles by checking if a visited neighbor is not the parent, indicating a cycle.

🧠 Conceptual

expert

Maximum Number of Edges in a Tree vs Graph

Which statement correctly compares the maximum number of edges in a tree and a graph with n nodes?

A A tree can have cycles, so it can have more edges than a graph.

B A tree with n nodes can have up to n*(n-1)/2 edges; a graph always has n-1 edges.

C Both tree and graph with n nodes always have the same number of edges, n-1.

D A tree with n nodes has exactly n-1 edges; a graph can have up to n*(n-1)/2 edges if undirected and simple.

💡 Hint

Recall the definitions of tree edges and maximum edges in simple graphs.

A tree with n nodes always has n-1 edges. A simple undirected graph can have up to n*(n-1)/2 edges connecting every pair of nodes.

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