Graph vs Tree Key Structural Difference in DSA Python - 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 graph is always directed, but a tree is always undirected.

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

C A tree allows cycles, but a graph never allows cycles.

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

💡 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 Graph vs Tree Edge Count Check

What is the output of the following Python code that checks edge counts for a graph and a tree?

DSA Python

def is_tree(num_nodes, edges):
    return len(edges) == num_nodes - 1

# Graph with 4 nodes and 4 edges
graph_edges = [(1,2), (2,3), (3,4), (4,1)]
# Tree with 4 nodes and 3 edges
tree_edges = [(1,2), (2,3), (3,4)]

print(is_tree(4, graph_edges))
print(is_tree(4, tree_edges))

A True\nTrue

B False\nTrue

C True\nFalse

D False\nFalse

💡 Hint

Recall the edge count property of trees.

A tree with n nodes must have exactly n-1 edges. The graph has 4 edges, so it is not a tree.

🔧 Debug

advanced

Identify the Error in Tree Cycle Check Code

What error does the following code produce when checking if a graph is a tree by detecting cycles?

DSA Python

def has_cycle(graph, node, visited, parent):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(graph, neighbor, visited, node):
                return True
        elif neighbor != parent:
            return True
    return False

graph = {1: [2], 2: [1, 3], 3: [2, 4]}
visited = set()
print(has_cycle(graph, 1, visited, -1))

A KeyError

B False

C TypeError

D True

💡 Hint

Check if all keys exist in the graph dictionary.

The graph dictionary does not have a key for node 3's neighbor 4, causing a KeyError when accessing graph[4].

❓ Predict Output

advanced

Output of BFS Traversal on Tree vs Graph

What is the output of the BFS traversal starting from node 1 on the following graph and tree?

DSA Python

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(graph[node])
    return order

graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2, 1]}
tree = {1: [2, 3], 2: [4], 3: [], 4: []}

print(bfs(graph, 1))
print(bfs(tree, 1))

A [1, 2, 3, 4]\n[1, 2, 3, 4]

B [1, 2, 3, 4]\n[1, 2, 3]

C [1, 3, 2, 4]\n[1, 2, 3, 4]

D [1, 2, 4, 3]\n[1, 2, 3, 4]

💡 Hint

Consider how BFS visits nodes level by level.

BFS visits nodes in order of their distance from the start. Both structures produce the same BFS order here.

🧠 Conceptual

expert

Why Trees Cannot Have Cycles but Graphs Can

Why is it impossible for a tree to have cycles, but graphs can have cycles?

A Because trees use only undirected edges, but graphs use only directed edges.

B Because trees have a fixed number of nodes, but graphs can have infinite nodes.

C Because trees are defined as connected acyclic graphs, while graphs have no such restriction.

D Because trees always have a root node, but graphs never have a root node.

💡 Hint

Think about the formal definition of a tree.

Trees are a special type of graph that must be connected and have no cycles by definition. Graphs do not have this restriction and can contain cycles.

Practice

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

easy

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

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

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

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

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 can have cycles or not.

2. Step 2: Analyze other options for correctness

   Graphs do not always have a root node, and trees do not have multiple edges between the same nodes. Also, graphs can be directed or undirected, and trees are usually undirected but can be represented as directed.

3. Final Answer:

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

4. Quick Check:

   Cycle presence = Tree no cycles, Graph can have cycles [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 syntax correctly represents an undirected tree using an adjacency list in Python?

easy

A. tree = {1: [2], 2: [3], 3: [1]}

B. tree = {1: [2, 3], 2: [3], 3: [1]}

C. tree = {1: [2, 3], 2: [1], 3: [1]}

D. tree = {1: [2, 3], 2: [1, 3], 3: [2]}

Solution

1. Step 1: Understand adjacency list for undirected tree

   In an undirected tree, edges are bidirectional. So if node 1 connects to 2 and 3, nodes 2 and 3 must connect back to 1.

2. Step 2: Check each option for bidirectional edges

   tree = {1: [2, 3], 2: [1], 3: [1]} shows node 1 connected to 2 and 3, and nodes 2 and 3 connected back to 1. Others miss some connections or add extra edges.

3. Final Answer:

   tree = {1: [2, 3], 2: [1], 3: [1]} -> Option C

4. Quick Check:

   Bidirectional edges in adjacency list = tree = {1: [2, 3], 2: [1], 3: [1]} [OK]

Hint: Undirected edges appear in both nodes' lists [OK]

Common Mistakes:

• Missing reverse connections in adjacency list
• Adding extra edges that create cycles
• Confusing directed and undirected adjacency lists

3. What will be the output of the following Python code representing a graph?

graph = {1: [2], 2: [3], 3: [1]}
visited = set()
def dfs(node):
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor)
dfs(1)
print(sorted(visited))

medium

A. []

B. [1, 2, 3]

C. [1]

D. [1, 2]

Solution

1. Step 1: Trace DFS starting from node 1

   DFS visits node 1, then its neighbor 2, then 2's neighbor 3, then 3's neighbor 1 which is already visited, so stops.

2. Step 2: Collect visited nodes and sort

   Visited nodes are {1, 2, 3}. Sorting gives [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option B

4. Quick Check:

   DFS visits all connected nodes = [1, 2, 3] [OK]

Hint: DFS visits all reachable nodes from start [OK]

Common Mistakes:

• Stopping DFS too early
• Not adding nodes to visited set
• Confusing order of visited nodes

4. Find the error in this Python code that tries to check if a graph is a tree:

def is_tree(graph):
    visited = set()
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor != parent:
                if neighbor in visited:
                    return False
                if not dfs(neighbor, node):
                    return False
        return True
    return dfs(0, -1) and len(visited) == len(graph)

medium

A. The DFS function does not return the result of recursive calls.

B. The graph keys should start from 1, not 0.

C. The visited set is not initialized properly.

D. The parent parameter is not used correctly.

Solution

1. Step 1: Analyze DFS recursive calls

   The DFS function calls itself recursively but does not return the result of these calls, so it ignores false returns from deeper calls.

2. Step 2: Identify missing return propagation

   Without returning the recursive call's result, the function always returns true at the end, missing cycle detection.

3. Final Answer:

   The DFS function does not return the result of recursive calls. -> Option A

4. Quick Check:

   Recursive return missing causes incorrect cycle detection [OK]

Hint: Always return recursive call results in DFS [OK]

Common Mistakes:

• Ignoring return values of recursive DFS calls
• Assuming node numbering starts at 0
• Misusing parent parameter in cycle check

5. Given a graph represented as an adjacency list, which condition must be true for it to be a tree?

hard

A. It must be connected and have exactly n-1 edges, where n is the number of nodes.

B. It must have no cycles and at least n edges.

C. It must be disconnected and have fewer than n-1 edges.

D. It must have cycles and exactly n edges.

Solution

1. Step 1: Recall tree properties

   A tree with n nodes must be connected (all nodes reachable) and have exactly n-1 edges to avoid cycles.

2. Step 2: Check each option against these properties

   It must be connected and have exactly n-1 edges, where n is the number of nodes. matches these conditions. Others either allow cycles, disconnectedness, or wrong edge counts.

3. Final Answer:

   It must be connected and have exactly n-1 edges, where n is the number of nodes. -> Option A

4. Quick Check:

   Tree = connected + edges = n-1 [OK]

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

Common Mistakes:

• Allowing cycles in a tree
• Confusing edge count with nodes
• Ignoring connectivity requirement