Why Graphs Exist and What Trees Cannot Model in DSA C++ - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why can't trees model all relationships?

Which of the following scenarios cannot be accurately represented by a tree structure?

A A social network where users can be friends with multiple others

B A company's organizational chart with one manager per employee

C A family tree showing parent-child relationships

D A file system directory with folders and subfolders

💡 Hint

Think about whether nodes can have multiple parents or cycles.

Trees cannot model relationships where nodes have multiple parents or cycles. Social networks have such connections, so they require graphs.

❓ Predict Output

intermediate

Output of graph adjacency list with cycles

What is the output of the following C++ code that builds a graph with cycles and prints adjacency lists?

DSA C++

std::unordered_map<int, std::vector<int>> graph;
graph[1] = {2, 3};
graph[2] = {3};
graph[3] = {1};
for (auto& [node, neighbors] : graph) {
    std::cout << node << ": ";
    for (int n : neighbors) std::cout << n << " ";
    std::cout << "\n";
}

A

1: 2 3 
2: 3 
3: 

B

1: 3 
2: 1 3 
3: 2 

C

1: 2 3 
2: 3 
3: 1 

D

1: 2 
2: 3 
3: 1 2 

💡 Hint

Check how edges are added and printed exactly.

The graph has edges 1->2, 1->3, 2->3, and 3->1, so adjacency lists print neighbors accordingly.

🔧 Debug

advanced

Detecting cycles in a graph vs tree

Given the following code snippet to detect cycles in a graph, what error will occur when run on a tree structure?

DSA C++

bool hasCycle(int node, std::unordered_map<int, std::vector<int>>& graph, std::unordered_set<int>& visited, int parent) {
    visited.insert(node);
    for (int neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {
            if (hasCycle(neighbor, graph, visited, node)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

// Called with hasCycle(root, graph, visited, -1);

A No error; returns false for trees without cycles

B Stack overflow due to infinite recursion

C Compilation error due to missing return statement

D Runtime error due to null pointer dereference

💡 Hint

Consider how the function handles visited nodes and parent tracking.

The function correctly detects cycles by tracking visited nodes and parent. Trees have no cycles, so it returns false without error.

🚀 Application

advanced

Modeling transportation networks

Which data structure best models a city's transportation network where intersections connect multiple roads and some roads form loops?

A Stack of intersections visited

B Linked list of intersections in order

C Binary tree with nodes as intersections

D Graph with nodes as intersections and edges as roads

💡 Hint

Think about multiple connections and loops in the network.

Graphs allow multiple connections per node and cycles, which matches transportation networks with loops and multiple roads.

🧠 Conceptual

expert

Why graphs are necessary beyond trees

Which statement best explains why graphs are necessary data structures beyond trees?

A Graphs restrict nodes to one parent, simplifying hierarchical data representation.

B Graphs allow nodes to have multiple parents and cycles, enabling modeling of complex relationships.

C Graphs are always acyclic, making them better for sorting data.

D Graphs store data in a linear order, unlike trees.

💡 Hint

Consider the structural differences between trees and graphs.

Graphs support multiple parents and cycles, which trees cannot, allowing modeling of complex, non-hierarchical relationships.

Practice

1. Why do we need graphs when trees already exist as data structures?

easy

A. Because graphs can represent connections between nodes in any pattern, including cycles and multiple links.

B. Because trees are faster to traverse than graphs.

C. Because trees can only store numbers, but graphs can store any data.

D. Because graphs use less memory than trees.

Solution

1. Step 1: Understand tree limitations

   Trees are hierarchical and cannot have cycles or multiple parents for a node.

2. Step 2: Understand graph capabilities

   Graphs allow cycles and multiple connections between nodes, modeling complex relationships.

3. Final Answer:

   Because graphs can represent connections between nodes in any pattern, including cycles and multiple links. -> Option A

4. Quick Check:

   Graphs model cycles and complex links = B [OK]

Hint: Graphs allow cycles; trees do not. Remember this difference [OK]

Common Mistakes:

• Thinking trees can have cycles
• Confusing data types stored with structure capabilities
• Assuming graphs always use less memory

2. Which of the following is the correct way to declare an undirected graph using adjacency list in C++?

easy

A. int graph[n][n];

B. std::vector<int> graph[n];

C. std::map graph;

D. std::vector graph(n);

Solution

1. Step 1: Identify adjacency list declaration

   Adjacency list uses vector of vectors or array of vectors to store neighbors.

2. Step 2: Check options

   std::vector graph(n); uses vector of vectors with size n, suitable for adjacency list.

3. Final Answer:

   std::vector graph(n); -> Option D

4. Quick Check:

   Adjacency list = vector of vectors [OK]

Hint: Use vector of vectors for adjacency list in modern C++ [OK]

Common Mistakes:

• Using map which is not adjacency list
• Using 2D array which is adjacency matrix
• Using vector<int> graph[n]; which is legacy C++

3. Consider the following C++ code snippet for an undirected graph:

std::vector graph(3);
graph[0].push_back(1);
graph[1].push_back(0);
graph[1].push_back(2);
graph[2].push_back(1);

for (int i = 0; i < 3; i++) {
    std::cout << i << ": ";
    for (int neighbor : graph[i]) {
        std::cout << neighbor << " ";
    }
    std::cout << std::endl;
}

What is the output?

medium

A. 0: 1
1: 0
2: 1 2

B. 0: 1
1: 2
2: 1 0

C. 0: 1
1: 0 2
2: 1

D. 0: 0 1
1: 0 2
2: 1

Solution

1. Step 1: Trace graph construction

   graph[0] has 1, graph[1] has 0 and 2, graph[2] has 1.

2. Step 2: Trace output loop

   Print neighbors for each node: 0->1, 1->0 2, 2->1.

3. Final Answer:

   0: 1 1: 0 2 2: 1 -> Option C

4. Quick Check:

   Adjacency list print matches 0: 1 1: 0 2 2: 1 [OK]

Hint: Follow push_back calls to build adjacency list [OK]

Common Mistakes:

• Mixing order of neighbors
• Confusing adjacency list with matrix output
• Missing symmetric edges in undirected graph

4. The following code attempts to add an edge in an undirected graph but has a bug:

void addEdge(std::vector& graph, int u, int v) {
    graph[u].push_back(v);
}

What is the bug and how to fix it?

medium

A. It should clear graph[u] before adding; fix by calling clear() first.

B. It adds edge only one way; fix by adding graph[v].push_back(u);

C. It uses push_back incorrectly; fix by using insert instead.

D. It should use graph[u][v] = 1; fix by using adjacency matrix.

Solution

1. Step 1: Identify undirected graph edge addition

   Undirected edges must be added both ways: u->v and v->u.

2. Step 2: Find missing edge addition

   Code adds only u->v, missing v->u, so add graph[v].push_back(u); to fix.

3. Final Answer:

   It adds edge only one way; fix by adding graph[v].push_back(u); -> Option B

4. Quick Check:

   Undirected edge needs both directions = C [OK]

Hint: Add edges both ways for undirected graphs [OK]

Common Mistakes:

• Adding edge only one way
• Using wrong vector method
• Confusing adjacency list with matrix

5. Which of the following real-world problems cannot be modeled by a tree but can be modeled by a graph?

medium

A. A social network where people can be friends with multiple others, including mutual friendships.

B. A company's organizational chart with one CEO and clear hierarchy.

C. A family tree showing parent-child relationships.

D. A file directory structure on a computer.

Solution

1. Step 1: Analyze tree model examples

   Family trees, org charts, and file directories are hierarchical with no cycles.

2. Step 2: Analyze social network structure

   Social networks have cycles and multiple connections, not fitting tree structure.

3. Final Answer:

   A social network where people can be friends with multiple others, including mutual friendships. -> Option A

4. Quick Check:

   Cycles and multiple links need graphs = A [OK]

Hint: Cycles and multiple parents mean graph, not tree [OK]

Common Mistakes:

• Thinking family trees have cycles
• Confusing hierarchy with network connections
• Assuming all relationships are one-to-one