Graph vs Tree Key Structural Difference in DSA C++ - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a tree node struct with an integer value.

DSA C++

struct TreeNode {
    int val;
    TreeNode* [1];
};

Drag options to blanks, or click blank then click option'

Anext

Bright

Cleft

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'next' which is common in linked lists, not trees.

In a binary tree node, the left child pointer is commonly named 'left'.

2fill in blank

medium

Complete the code to add an edge between two nodes in an undirected graph represented by adjacency list.

DSA C++

void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back([1]);
    adj[v].push_back(u);
}

Drag options to blanks, or click blank then click option'

Av

Bu

Cadj

Dedge

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing u instead of v, which adds a self-loop.

To add an edge from u to v, we push v into u's adjacency list.

3fill in blank

hard

Fix the error in the code that checks if a graph has a cycle using DFS.

DSA C++

bool dfs(int node, int parent, vector<int> adj[], vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited)) return true;
        } else if (neighbor != [1]) {
            return true;
        }
    }
    return false;
}

Drag options to blanks, or click blank then click option'

Anode

Bparent

Cneighbor

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing neighbor with node instead of parent.

When checking for a cycle, we ignore the edge back to the parent node.

4fill in blank

hard

Fill both blanks to create a function that checks if a graph is a tree by verifying edges and connectivity.

DSA C++

bool isTree(int V, vector<int> adj[]) {
    vector<bool> visited(V, false);
    int edgeCount = 0;
    for (int i = 0; i < V; i++) {
        edgeCount += adj[i].size();
    }
    if (edgeCount / [1] != V - 1) return false;
    dfs(0, -1, adj, visited);
    for (bool v : visited) {
        if (!v) return [2];
    }
    return true;
}

Drag options to blanks, or click blank then click option'

A2

Btrue

Cfalse

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Not dividing edge count by 2.

Returning true when nodes are unvisited.

A tree with V nodes has exactly V-1 edges, so edgeCount must be divided by 2 (undirected edges counted twice). Also, if any node is not visited, the graph is not connected, so return false.

5fill in blank

hard

Fill all three blanks to implement BFS traversal of a graph starting from node 0.

DSA C++

void bfs(int start, vector<int> adj[], vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = [1];
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = [2];
                q.[3](neighbor);
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Atrue

Bfalse

Cpush

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited as false.

Using pop instead of push to add neighbors.

We mark nodes as visited by setting visited[node] = true. We add neighbors to the queue using push.

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