Graph vs Tree Key Structural Difference in DSA Java - Build Both Approaches

Graph vs Tree Key Structural Difference

📖 Scenario: Imagine you are organizing a family reunion and a city map. The family reunion represents a tree structure where each person has a clear parent-child relationship. The city map represents a graph where locations are connected in many ways, including loops.

🎯 Goal: You will create simple Java code to represent a tree and a graph using adjacency lists. Then, you will identify the key structural difference by checking if the graph contains cycles or not.

📋 What You'll Learn

Create a tree using adjacency lists with 4 nodes

Create a graph using adjacency lists with 4 nodes including a cycle

Add a boolean variable hasCycle to indicate if the graph has cycles

Write code to detect if the graph has a cycle

Print the adjacency lists and the cycle detection result

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like family trees or file systems. Graphs are used to represent networks like city maps or social connections.

💼 Career

Understanding the difference between trees and graphs is fundamental for software engineers working with data structures, algorithms, and network analysis.

1

Create the tree adjacency list

Create a Java Map<Integer, List<Integer>> called tree with these exact entries: 1: [2, 3], 2: [4], 3: [], 4: []

DSA Java

// Your code here to create the tree adjacency list

Hint

Use a HashMap to store adjacency lists. Use Arrays.asList for children nodes.

2

Create the graph adjacency list with a cycle

Add a Java Map<Integer, List<Integer>> called graph with these exact entries: 1: [2, 3], 2: [4], 3: [1], 4: []

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map> tree = new HashMap();
        tree.put(1, Arrays.asList(2, 3));
        tree.put(2, Arrays.asList(4));
        tree.put(3, Collections.emptyList());
        tree.put(4, Collections.emptyList());

        // Create graph adjacency list with a cycle
        // Your code here
    }
}

Hint

Notice the edge from node 3 back to node 1 creates a cycle.

3

Add cycle detection logic

Add a boolean variable hasCycle and write a method detectCycle that takes the graph and returns true if there is a cycle, otherwise false. Call hasCycle = detectCycle(graph) inside main.

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map> tree = new HashMap();
        tree.put(1, Arrays.asList(2, 3));
        tree.put(2, Arrays.asList(4));
        tree.put(3, Collections.emptyList());
        tree.put(4, Collections.emptyList());

        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4));
        graph.put(3, Arrays.asList(1));
        graph.put(4, Collections.emptyList());

        // Add boolean hasCycle and call detectCycle(graph)
        // Your code here
    }

    // Add detectCycle method here
}

Hint

Use depth-first search with a recursion stack to detect cycles in the graph.

4

Print adjacency lists and cycle detection result

Print the tree adjacency list, the graph adjacency list, and the value of hasCycle using System.out.println.

DSA Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map> tree = new HashMap();
        tree.put(1, Arrays.asList(2, 3));
        tree.put(2, Arrays.asList(4));
        tree.put(3, Collections.emptyList());
        tree.put(4, Collections.emptyList());

        Map> graph = new HashMap();
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4));
        graph.put(3, Arrays.asList(1));
        graph.put(4, Collections.emptyList());

        boolean hasCycle = detectCycle(graph);

        // Print tree, graph, and hasCycle
        // Your code here
    }

    private static boolean detectCycle(Map> graph) {
        Set visited = new HashSet();
        Set recStack = new HashSet();

        for (Integer node : graph.keySet()) {
            if (dfs(node, graph, visited, recStack)) {
                return true;
            }
        }
        return false;
    }

    private static boolean dfs(Integer node, Map> graph, Set visited, Set recStack) {
        if (recStack.contains(node)) {
            return true;
        }
        if (visited.contains(node)) {
            return false;
        }

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

        for (Integer neighbor : graph.get(node)) {
            if (dfs(neighbor, graph, visited, recStack)) {
                return true;
            }
        }

        recStack.remove(node);
        return false;
    }
}

Hint

Use System.out.println to print the maps and the boolean variable.

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

   A tree is a special type of graph that does not contain any cycles. Graphs, however, can have cycles.

2. Step 2: Analyze other options for correctness

   Graphs do not always have a root node; trees do. Trees do not have multiple edges between the same nodes. Graphs can be directed or undirected, same as trees.

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 directed and undirected properties

2. Which of the following Java declarations correctly represents a tree node with children stored in a list?

easy

A. class Node { int val; Node left, right; }

B. class Node { int val; Map edges; }

C. class Node { int val; Node parent; }

D. class Node { int val; List<Node> children; }

Solution

1. Step 1: Identify tree node with multiple children

   A tree node with multiple children is best represented by a list of child nodes, as in class Node { int val; List<Node> children; }.

2. Step 2: Check other options for correctness

   class Node { int val; Node left, right; } is a binary tree node (only left and right). class Node { int val; Node parent; } stores parent, not children. class Node { int val; Map edges; } uses a map for edges, more typical in graphs.

3. Final Answer:

   class Node { int val; List<Node> children; } -> Option D

4. Quick Check:

   Multiple children stored in List = class Node { int val; List<Node> children; } [OK]

Hint: Use List<Node> for multiple children in tree nodes [OK]

Common Mistakes:

• Using only left and right for non-binary trees
• Confusing parent pointer with children list
• Using Map for tree edges instead of graph

3. Consider the following Java code snippet representing a graph and a tree. What will be the output when checking if the graph has cycles?

class GraphNode {
  int val;
  List<GraphNode> neighbors = new ArrayList<>();
}

boolean hasCycle(GraphNode node, Set<GraphNode> visited, Set<GraphNode> recStack) {
  if (recStack.contains(node)) return true;
  if (visited.contains(node)) return false;
  visited.add(node);
  recStack.add(node);
  for (GraphNode neighbor : node.neighbors) {
    if (hasCycle(neighbor, visited, recStack)) return true;
  }
  recStack.remove(node);
  return false;
}

// Setup
GraphNode a = new GraphNode(); a.val = 1;
GraphNode b = new GraphNode(); b.val = 2;
GraphNode c = new GraphNode(); c.val = 3;
a.neighbors.add(b);
b.neighbors.add(c);
c.neighbors.add(a); // cycle here

System.out.println(hasCycle(a, new HashSet<>(), new HashSet<>()));

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Understand the cycle detection logic

   The method uses recursion with a recursion stack to detect cycles. If a node is revisited in the current recursion path, it returns true.

2. Step 2: Analyze the graph structure

   Nodes a -> b -> c -> a form a cycle. So the method will detect this cycle and return true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Cycle detected in graph = true [OK]

Hint: Cycle if recursion revisits node in current path [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming no cycles in graphs by default
• Confusing visited set with recursion stack

4. The following Java method is intended to check if a given tree node has cycles. Identify the error:

boolean hasCycle(TreeNode node, Set<TreeNode> visited) {
  if (visited.contains(node)) return true;
  visited.add(node);
  for (TreeNode child : node.children) {
    if (hasCycle(child, visited)) return true;
  }
  return false;
}

medium

A. It uses a Set which is not allowed for trees.

B. It does not track recursion stack, so false positives possible.

C. It should check for null children before recursion.

D. It incorrectly returns false when a cycle is found.

Solution

1. Step 1: Understand cycle detection in trees

   Cycle detection requires tracking nodes in the current recursion path (recursion stack), not just visited nodes.

2. Step 2: Identify missing recursion stack usage

   This method only uses visited set, so it may wrongly detect cycles if a node is visited from different branches (false positives).

3. Final Answer:

   It does not track recursion stack, so false positives possible. -> Option B

4. Quick Check:

   Missing recursion stack causes false positives [OK]

Hint: Track recursion stack to avoid false cycle detection [OK]

Common Mistakes:

• Using only visited set for cycle detection in trees
• Not checking for null children (usually safe)
• Misinterpreting return values

5. You have a graph represented by adjacency lists. You want to check if it is a tree. Which combination of conditions must be true for the graph to be a tree?

hard

A. The graph is connected and has exactly (n-1) edges, where n is the number of nodes.

B. The graph has no cycles and exactly n edges, where n is the number of nodes.

C. The graph is connected and has cycles but fewer than n edges.

D. The graph is disconnected but has no cycles.

Solution

1. Step 1: Recall tree properties in graph terms

   A tree is a connected graph with no cycles and exactly (n-1) edges for n nodes.

2. Step 2: Analyze each option

   The graph is connected and has exactly (n-1) edges, where n is the number of nodes. matches the definition. The graph has no cycles and exactly n edges, where n is the number of nodes. has wrong edge count. The graph is connected and has cycles but fewer than n edges. allows cycles. The graph is disconnected but has no cycles. is disconnected.

3. Final Answer:

   The graph is connected and has exactly (n-1) edges, where n is the number of nodes. -> Option A

4. Quick Check:

   Connected + edges = n-1 means tree [OK]

Hint: Tree edges = nodes - 1 and graph must be connected [OK]

Common Mistakes:

• Counting edges equal to nodes as tree
• Ignoring connectivity requirement
• Allowing cycles in trees