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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Key Structural Difference Between Graph and Tree

Which of the following statements 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 trees and graphs.

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 and Tree Edge Count Check

Consider a graph and a tree each with 5 nodes. What is the number of edges in the tree?

DSA C++

int nodes = 5;
int treeEdges = nodes - 1;
int graphEdges = 7; // example graph edges
std::cout << treeEdges << std::endl;

A 4

B 5

C 6

D 7

💡 Hint

Recall the formula for edges in a tree with n nodes.

A tree with n nodes always has n-1 edges.

🔧 Debug

advanced

Identify the Error in Tree Cycle Check Code

What error will occur when running the following C++ code that tries to detect a cycle in a tree represented as an adjacency list?

DSA C++

std::vector<std::vector<int>> adj = {{1}, {0, 2}, {1, 3}, {2, 1}};
std::vector<bool> visited(4, false);

bool hasCycle(int node, int parent) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (hasCycle(neighbor, node)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

int main() {
    bool cycle = hasCycle(0, -1);
    std::cout << (cycle ? "Cycle detected" : "No cycle") << std::endl;
    return 0;
}

A No output, infinite recursion causing stack overflow

B Outputs "No cycle"

C Outputs "Cycle detected"

D Compilation error due to missing function prototype

💡 Hint

Check the adjacency list for cycles and how the function detects them.

The adjacency list contains a cycle between nodes 1, 2, and 3, so the function correctly detects a cycle and outputs "Cycle detected".

❓ Predict Output

advanced

Output of BFS Traversal on Tree vs Graph

Given the following adjacency list for a graph, what is the BFS traversal order starting from node 0?

DSA C++

std::vector<std::vector<int>> adj = {{1, 2}, {0, 3}, {0, 3}, {1, 2}};

std::vector<int> bfs(int start) {
    std::vector<int> order;
    std::queue<int> q;
    std::vector<bool> visited(adj.size(), false);
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return order;
}

int main() {
    auto order = bfs(0);
    for (int n : order) std::cout << n << " ";
    return 0;
}

A 0 3 1 2

B 0 1 2 3

C 0 1 3 2

D 0 2 1 3

💡 Hint

BFS visits neighbors level by level in the order they appear in adjacency list.

Starting at 0, neighbors 1 and 2 are visited in order. Then neighbors of 1 (3) and 2 (3) are visited, but 3 is visited once.

🧠 Conceptual

expert

Why Trees Have Exactly One Path Between Any Two Nodes

Why does a tree have exactly one simple path between any two nodes?

A Because trees always have directed edges that restrict path choices.

B Because trees have cycles that allow multiple paths but only one is chosen.

C Because trees are disconnected graphs with isolated nodes.

D Because trees are connected and acyclic, so no alternative paths exist between nodes.

💡 Hint

Think about what acyclic and connected mean for paths.

Since trees are connected and have no cycles, there is only one unique path between any two 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

   A tree is a special type of graph that does not contain any cycles, meaning no path loops back to the same node.

2. Step 2: Compare cycle allowance in graphs

   Graphs can have cycles, meaning nodes can be connected in loops, unlike trees.

3. Final Answer:

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

4. Quick Check:

   Tree = no cycles, Graph = cycles allowed [OK]

Hint: Trees never loop back; graphs can have loops [OK]

Common Mistakes:

• Thinking graphs always have a root node
• Believing trees can have multiple edges between same nodes
• Assuming all graphs are directed

2. Which of the following C++ declarations correctly represents a tree node with integer data and pointers to children?

easy

A. struct Node { int data; Node* parent; Node* sibling; };

B. struct Node { int data; vector neighbors; };

C. struct Node { int data; Node* left; Node* right; };

D. struct Node { int data; Node* next; };

Solution

1. Step 1: Identify typical tree node structure

   A tree node usually has data and pointers to its children, commonly left and right for binary trees.

2. Step 2: Match declaration to tree node

   struct Node { int data; Node* left; Node* right; }; shows integer data and two child pointers, matching a binary tree node structure.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option C

4. Quick Check:

   Tree node = data + child pointers [OK]

Hint: Tree nodes have child pointers, not neighbor lists [OK]

Common Mistakes:

• Confusing graph neighbors with tree children
• Using sibling or next pointers incorrectly for trees
• Missing child pointers in node structure

3. Consider the following C++ code snippet representing a graph and a tree. What will be the output?

struct Node {
  int val;
  vector neighbors;
};

int countEdges(Node* root, unordered_set& visited) {
  if (!root || visited.count(root)) return 0;
  visited.insert(root);
  int edges = root->neighbors.size();
  for (auto n : root->neighbors) {
    edges += countEdges(n, visited);
  }
  return edges;
}

int main() {
  Node a{1}, b{2}, c{3};
  a.neighbors = {&b};
  b.neighbors = {&c};
  c.neighbors = {};
  unordered_set visited;
  cout << countEdges(&a, visited) << endl;
  return 0;
}

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Analyze graph structure and edges

   Node a connects to b (1 edge), b connects to c (1 edge), c has no neighbors. Total edges = 2.

2. Step 2: Trace recursive countEdges calls

   Starting at a, edges = 1 + countEdges(b), at b edges = 1 + countEdges(c), at c edges = 0. Sum = 1 + 1 + 0 = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Edges counted = 2 [OK]

Hint: Count neighbors recursively to sum edges [OK]

Common Mistakes:

• Counting nodes instead of edges
• Double counting edges due to cycles
• Ignoring visited set causing infinite recursion

4. The following code attempts to check if a given graph is a tree. Identify the bug:

bool isTree(Node* root, unordered_set& visited, Node* parent) {
  if (!root) return true;
  if (visited.count(root)) return false;
  visited.insert(root);
  for (auto n : root->neighbors) {
    if (n != parent && !isTree(n, visited, root)) return false;
  }
  return true;
}

medium

A. It misses checking for null root.

B. It does not handle cycles correctly.

C. It uses wrong data type for visited nodes.

D. It does not check if all nodes are connected.

Solution

1. Step 1: Understand what the code checks

   The code detects cycles by checking if a node is visited again except the parent, which is correct.

2. Step 2: Identify missing connectivity check

   However, it does not verify if all nodes are reachable from root, so disconnected graphs may pass incorrectly.

3. Final Answer:

   It does not check if all nodes are connected. -> Option D

4. Quick Check:

   Connectivity check missing = bug [OK]

Hint: Check connectivity separately to confirm tree [OK]

Common Mistakes:

• Assuming cycle check covers connectivity
• Ignoring visited set usage
• Confusing parent check logic

5. You have a connected undirected graph with N nodes and N-1 edges. Which statement correctly explains why this graph must be a tree?

hard

A. Because it has exactly one cycle, making it a tree.

B. Because it is connected and has no cycles, so it is a tree.

C. Because it has fewer edges than nodes, so it is a tree.

D. Because it has exactly N edges, which defines a tree.

Solution

1. Step 1: Recall tree edge and node relationship

   A tree with N nodes always has exactly N-1 edges and is connected without cycles.

2. Step 2: Analyze given graph properties

   The graph is connected and has N-1 edges, so it cannot have cycles and must be a tree.

3. Final Answer:

   Because it is connected and has no cycles, so it is a tree. -> Option B

4. Quick Check:

   Connected + N-1 edges = tree [OK]

Hint: Connected + N-1 edges means tree [OK]

Common Mistakes:

• Thinking N edges define a tree
• Assuming presence of cycles with N-1 edges
• Confusing edge count with node count