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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why can't trees model all relationships?

Which of the following best explains why trees cannot model all types of relationships in data?

A Trees only allow nodes to have exactly two children, limiting their use.

B Trees are too complex and have too many connections to represent simple relationships.

C Trees always require weighted edges, which are not needed in many relationships.

D Trees cannot represent cycles or multiple parent nodes, which are common in real-world relationships.

💡 Hint

Think about what happens if a node has more than one parent or if there is a loop.

Trees are hierarchical structures where each node has exactly one parent except the root. They cannot represent cycles or nodes with multiple parents, which are common in many real-world relationships like social networks or road maps. Graphs allow these complex connections.

❓ Predict Output

intermediate

Output of graph adjacency list with cycles

What is the output of the following Java code that creates a graph with cycles and prints adjacency lists?

DSA Java

import java.util.*;

public class GraphExample {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(3));
        graph.put(3, Arrays.asList(1));

        for (int node : graph.keySet()) {
            System.out.print(node + " -> ");
            for (int neighbor : graph.get(node)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

A

1 -> 2 3 
2 -> 1 3 
3 -> 1 

B

1 -> 2 3 
2 -> 3 
3 -> 1 

C

1 -> 3 
2 -> 3 
3 -> 1 2 

D

1 -> 2 
2 -> 3 
3 -> 1 

💡 Hint

Look carefully at how neighbors are assigned for each node.

The graph is represented as a map where each node points to a list of neighbors. Node 1 points to 2 and 3, node 2 points to 3, and node 3 points back to 1, creating a cycle. The output prints each node followed by its neighbors.

🔧 Debug

advanced

Identify the error in graph cycle detection code

What error will the following Java code produce when trying to detect a cycle in a graph?

DSA Java

import java.util.*;

public class CycleCheck {
    private Map<Integer, List<Integer>> graph;
    private Set<Integer> visited = new HashSet<>();
    private Set<Integer> recStack = new HashSet<>();

    public CycleCheck(Map<Integer, List<Integer>> graph) {
        this.graph = graph;
    }

    public boolean hasCycle(int node) {
        if (recStack.contains(node)) return true;
        if (visited.contains(node)) return false;

        visited.add(node);
        recStack.add(node);

        for (int neighbor : graph.get(node)) {
            if (hasCycle(neighbor)) return true;
        }

        recStack.remove(node);
        return false;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        g.put(1, Arrays.asList(2));
        g.put(2, Arrays.asList(3));
        g.put(3, Arrays.asList(1));

        CycleCheck cc = new CycleCheck(g);
        System.out.println(cc.hasCycle(1));
    }
}

A No error; the code correctly detects cycles and prints true.

B StackOverflowError due to infinite recursion caused by cycles.

C NullPointerException because graph.get(node) returns null for nodes without neighbors.

D Compilation error because of missing return statement.

💡 Hint

Check how the recursion and visited sets prevent infinite loops.

The code uses recursion with a recursion stack and visited set to detect cycles. It returns true if a node is found in the recursion stack again, indicating a cycle. The code correctly detects the cycle 1->2->3->1 and prints true without errors.

📝 Syntax

advanced

Which option causes a syntax error in graph adjacency list creation?

Which of the following Java code snippets will cause a syntax error when creating a graph adjacency list?

A Map<Integer, List<Integer>> graph = new HashMap<>(); graph.put(1, Arrays.asList(2, 3));

B Map<Integer, List<Integer>> graph = new HashMap<>(); graph.put(1, new ArrayList<>(Arrays.asList(2, 3)));

C Map<Integer, List<Integer>> graph = new HashMap<>(); graph.put(1, new ArrayList(2, 3));

D Map<Integer, List<Integer>> graph = new HashMap<>(); graph.put(1, List.of(2, 3));

💡 Hint

Check the constructors available for ArrayList.

ArrayList does not have a constructor that takes multiple elements directly. Option C tries to call new ArrayList(2, 3), which is invalid syntax. The other options use valid ways to create lists.

🚀 Application

expert

Modeling a social network with graphs vs trees

You want to model a social network where users can follow multiple other users and cycles can exist (e.g., user A follows B, B follows C, and C follows A). Which data structure is best and why?

A Use a graph because it can represent cycles and multiple connections between users.

B Use a tree because it naturally models hierarchical relationships and is simpler to traverse.

C Use a linked list because it efficiently stores sequences of users.

D Use an array because it provides fast access to user data.

💡 Hint

Think about whether cycles and multiple parents are allowed in the data.

Social networks have complex relationships with cycles and multiple connections. Trees cannot represent cycles or multiple parents. Graphs allow these connections and are the best choice to model such networks.

Practice

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

easy

A. Because graphs use less memory than trees.

B. Because graphs can represent connections between nodes in any pattern, including cycles and multiple parents, which trees cannot.

C. Because trees cannot store any data in nodes.

D. Because trees are slower to traverse than graphs.

Solution

1. Step 1: Understand tree structure limitations

   Trees have a strict hierarchy where each node has exactly one parent except the root, and no cycles are allowed.

2. Step 2: Understand graph flexibility

   Graphs allow nodes to connect in any way, including cycles and multiple parents, which trees cannot model.

3. Final Answer:

   Because graphs can represent connections between nodes in any pattern, including cycles and multiple parents, which trees cannot. -> Option B

4. Quick Check:

   Graphs model complex connections = D [OK]

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

Common Mistakes:

• Thinking trees can have cycles
• Confusing memory use between trees and graphs
• Believing trees cannot store data

2. Which of the following is the correct way to declare a graph adjacency list in Java using a HashMap?

easy

A. HashMap graph = new HashMap<>();

B. HashMap graph = new HashMap<>();

C. HashMap graph = new HashMap<>();

D. HashMap graph = new HashMap<>();

Solution

1. Step 1: Identify correct key and value types for adjacency list

   Keys are node identifiers (Integer), values are lists of connected nodes (List<Integer>).

2. Step 2: Check syntax correctness

   HashMap graph = new HashMap<>(); uses HashMap which correctly represents adjacency list.

3. Final Answer:

   HashMap graph = new HashMap<>(); -> Option D

4. Quick Check:

   Adjacency list uses map of node to list [OK]

Hint: Adjacency list maps node to list of neighbors [OK]

Common Mistakes:

• Using primitive int as generic type
• Mapping node to single Integer instead of list
• Using wrong generic types like String when nodes are integers

3. Consider the following Java code snippet that builds a graph and prints its adjacency list:

import java.util.*;
public class GraphExample {
    public static void main(String[] args) {
        HashMap graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(1, 4));
        graph.put(3, Arrays.asList(1));
        graph.put(4, Arrays.asList(2));
        for (int node : graph.keySet()) {
            System.out.print(node + " -> ");
            for (int neighbor : graph.get(node)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

What is the output of this program?

medium

A. 1 -> 2 3
2 -> 1 4
3 -> 1
4 -> 2

B. 1 -> 3 2
2 -> 4 1
3 -> 1
4 -> 2

C. 1 -> 2 3
2 -> 4 1
3 -> 1
4 -> 2

D. 1 -> 2 3
2 -> 1 4
3 -> 4
4 -> 2

Solution

1. Step 1: Analyze graph construction

   Node 1 connects to 2 and 3; 2 connects to 1 and 4; 3 connects to 1; 4 connects to 2.

2. Step 2: Trace print output

   For each node, print node followed by neighbors in order stored in list.

3. Final Answer:

   1 -> 2 3 2 -> 1 4 3 -> 1 4 -> 2 -> Option A

4. Quick Check:

   Printed adjacency matches stored lists = A [OK]

Hint: Print neighbors in stored order for each node [OK]

Common Mistakes:

• Mixing neighbor order
• Printing wrong neighbors for nodes
• Confusing node keys with neighbor values

4. The following Java code attempts to add an edge between two nodes in an undirected graph represented by an adjacency list. Find the error:

void addEdge(HashMap graph, int u, int v) {
    graph.get(u).add(v);
    graph.get(v).add(u);
}

medium

A. The code uses List<Integer> instead of Set<Integer> for neighbors.

B. The code should remove edges instead of adding them.

C. The code does not check if nodes u and v exist in the graph before adding edges.

D. The code incorrectly adds edges only in one direction.

Solution

1. Step 1: Check for node existence before adding edges

   graph.get(u) or graph.get(v) may return null if nodes are not present, causing NullPointerException.

2. Step 2: Identify missing null checks or initialization

   Code should verify nodes exist or initialize adjacency lists before adding neighbors.

3. Final Answer:

   The code does not check if nodes u and v exist in the graph before adding edges. -> Option C

4. Quick Check:

   Missing node existence check causes error = B [OK]

Hint: Always check nodes exist before adding edges [OK]

Common Mistakes:

• Assuming nodes always exist in graph
• Confusing undirected with directed edges
• Ignoring possibility of NullPointerException

5. You want to model a social network where users can follow each other in any pattern, including mutual follows and cycles. Why is a graph a better choice than a tree for this model, and how would you represent it in Java?

hard

A. Because trees cannot represent cycles or mutual connections; use a HashMap to store user IDs and their followers.

B. Because trees are faster to search; use a TreeMap to store user IDs.

C. Because trees allow multiple parents; use a HashSet<Integer> to store users.

D. Because trees prevent cycles; use an array to store user connections.

Solution

1. Step 1: Understand social network connections

   Users can follow each other in any pattern, including cycles and mutual follows, which trees cannot model.

2. Step 2: Choose graph representation in Java

   Use HashMap to map each user ID to a list of users they follow.

3. Final Answer:

   Because trees cannot represent cycles or mutual connections; use a HashMap to store user IDs and their followers. -> Option A

4. Quick Check:

   Graphs model cycles; HashMap with lists stores connections [OK]

Hint: Use graph with adjacency list for mutual and cyclic connections [OK]

Common Mistakes:

• Choosing tree which disallows cycles
• Using TreeMap or array which limits connection types
• Confusing followers with parents in tree