Graph vs Tree Key Structural Difference in DSA C++ - 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 everyone is connected without loops, and the city map represents a graph where roads can connect places in many ways, including loops.

🎯 Goal: You will create simple representations of a tree and a graph using adjacency lists in C++. Then, you will add a configuration to check if the structure has cycles (loops). Finally, you will print whether the structure is a tree or a graph based on the presence of cycles.

📋 What You'll Learn

Create an adjacency list for a tree with 4 nodes and edges: 1-2, 1-3, 3-4

Create an adjacency list for a graph with 4 nodes and edges: 1-2, 1-3, 3-4, 4-1 (which forms a cycle)

Add a boolean variable called hasCycle initialized to false

Implement a simple cycle detection logic by checking if any node connects back to a previously visited node

Print "Tree structure: No cycles detected" if no cycle, else "Graph structure: Cycle detected"

💡 Why This Matters

🌍 Real World

Trees are used in family trees, file systems, and organizational charts where no loops exist. Graphs model city maps, social networks, and transportation routes where loops and multiple connections exist.

💼 Career

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

1

Create adjacency list for a tree

Create a variable called tree as a std::vector> with 5 elements (index 0 unused). Add edges: 1 connected to 2, 1 connected to 3, and 3 connected to 4.

DSA C++

#include 
#include 

int main() {
    // Create adjacency list for tree with 5 nodes
    // Your code here
    return 0;
}

Hint

Use a vector of vectors to represent adjacency. Remember to add edges both ways since this is an undirected tree.

2

Create adjacency list for a graph with a cycle and add cycle flag

Create a variable called graph as a std::vector> with 5 elements (index 0 unused). Add edges: 1 connected to 2, 1 connected to 3, 3 connected to 4, and 4 connected to 1 (forming a cycle). Also, create a boolean variable called hasCycle and set it to false.

DSA C++

#include 
#include 

int main() {
    std::vector> tree(5);
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[3].push_back(4);
    tree[4].push_back(3);

    // Create adjacency list for graph with cycle
    // Create boolean hasCycle and set to false
    // Your code here

    return 0;
}

Hint

Remember to add edges both ways for the graph too. The edge 4-1 creates a cycle.

3

Detect cycle in the graph

Write code to detect a cycle in the graph by using a std::vector visited(5, false) and a simple loop. For each node from 1 to 4, if it is visited, set hasCycle to true. (This is a simplified check for demonstration.)

DSA C++

#include 
#include 

int main() {
    std::vector> tree(5);
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[3].push_back(4);
    tree[4].push_back(3);

    std::vector> graph(5);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);
    graph[4].push_back(1);
    graph[1].push_back(4);

    bool hasCycle = false;

    std::vector visited(5, false);
    // Your code here

    return 0;
}

Hint

This is a simplified cycle detection for demonstration. Normally, cycle detection is more complex.

4

Print if structure is tree or graph based on cycle detection

Write a std::cout statement that prints "Tree structure: No cycles detected" if hasCycle is false, else prints "Graph structure: Cycle detected".

DSA C++

#include 
#include 

int main() {
    std::vector> tree(5);
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[3].push_back(4);
    tree[4].push_back(3);

    std::vector> graph(5);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);
    graph[4].push_back(1);
    graph[1].push_back(4);

    bool hasCycle = false;

    std::vector visited(5, false);
    for (int node = 1; node <= 4; ++node) {
        if (visited[node]) {
            hasCycle = true;
            break;
        }
        visited[node] = true;
    }

    if (!hasCycle) {
        // Print tree message
    } else {
        // Print graph message
    }

    return 0;
}

Hint

Use an if-else statement to print the correct message based on hasCycle.

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