Graph vs Tree Key Structural Difference in DSA Javascript - Trade-offs & Analysis

Mental Model

A tree is a special kind of graph with no loops and exactly one path between nodes. A graph is more general and can have loops and multiple paths.

Analogy: Think of a family tree where each person has one parent path up, no cycles. A graph is like a city map where roads can loop and connect in many ways.

Tree:
  1
 / \
2   3

Graph:
1 -> 2 -> 3
↑         ↓
←---------

Dry Run Walkthrough

Input: Graph with nodes 1, 2, 3 and edges 1->2, 2->3, 3->1; Tree with nodes 1, 2, 3 and edges 1->2, 1->3

Goal: Show the key structural difference: tree has no cycles, graph can have cycles

Step 1: Look at tree edges connecting nodes 1, 2, 3

Tree:
1 -> 2
1 -> 3
Graph:
1 -> 2 -> 3
↑         ↓
←---------

Why: To see how nodes connect in a tree without loops

Step 2: Check if any path loops back in tree

Tree:
1 -> 2
1 -> 3
No cycles found
Graph:
1 -> 2 -> 3
↑         ↓
←---------

Why: Trees must have no cycles, so no node revisited

Step 3: Check if any path loops back in graph

Graph:
1 -> 2 -> 3
↑         ↓
←--------- (cycle detected)

Why: Graphs can have cycles, so node 1 is revisited via 3

Result:

Tree:
1 -> 2
1 -> 3
No cycles, one path between nodes
Graph:
1 -> 2 -> 3
↑         ↓
←---------
Cycle exists, multiple paths possible

Annotated Code

DSA Javascript

class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(v) {
    if (!this.adjList.has(v)) this.adjList.set(v, []);
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w);
  }

  hasCycleUtil(v, visited, recStack) {
    visited[v] = true;
    recStack[v] = true;

    for (const neighbor of this.adjList.get(v)) {
      if (!visited[neighbor] && this.hasCycleUtil(neighbor, visited, recStack)) {
        return true;
      } else if (recStack[neighbor]) {
        return true;
      }
    }

    recStack[v] = false;
    return false;
  }

  hasCycle() {
    const visited = {};
    const recStack = {};
    for (const vertex of this.adjList.keys()) {
      if (!visited[vertex]) {
        if (this.hasCycleUtil(vertex, visited, recStack)) {
          return true;
        }
      }
    }
    return false;
  }

  print() {
    let result = '';
    for (const [key, values] of this.adjList.entries()) {
      result += `${key} -> ${values.join(', ')}\n`;
    }
    return result.trim();
  }
}

// Tree example
const tree = new Graph();
tree.addVertex(1);
tree.addVertex(2);
tree.addVertex(3);
tree.addEdge(1, 2);
tree.addEdge(1, 3);

// Graph example with cycle
const graph = new Graph();
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 1);

console.log('Tree structure:');
console.log(tree.print());
console.log('Tree has cycle? ' + tree.hasCycle());

console.log('\nGraph structure:');
console.log(graph.print());
console.log('Graph has cycle? ' + graph.hasCycle());

visited[v] = true; recStack[v] = true;

Mark current node as visited and add to recursion stack to detect cycles

for (const neighbor of this.adjList.get(v)) {

Traverse all neighbors to check for cycles

if (!visited[neighbor] && this.hasCycleUtil(neighbor, visited, recStack)) { return true; }

Recursively check unvisited neighbors for cycles

else if (recStack[neighbor]) { return true; }

If neighbor is in recursion stack, cycle detected

recStack[v] = false;

Remove node from recursion stack after exploring neighbors

for (const vertex of this.adjList.keys()) { if (!visited[vertex]) { if (this.hasCycleUtil(vertex, visited, recStack)) { return true; } } }

Check all nodes to detect cycle in disconnected graphs

Output

Tree structure:

1 -> 2, 3

2 -> 

3 -> 

Tree has cycle? false



Graph structure:

1 -> 2

2 -> 3

3 -> 1

Graph has cycle? true

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during cycle detection

Space: O(V) for visited and recursion stack arrays to track nodes

vs Alternative: Naive cycle detection might check all paths repeatedly causing exponential time; DFS with recursion stack is efficient

Edge Cases

Empty graph

No vertices or edges, so no cycles detected

DSA Javascript

for (const vertex of this.adjList.keys()) { if (!visited[vertex]) {

Single node with no edges

No cycles because no edges exist

DSA Javascript

for (const vertex of this.adjList.keys()) { if (!visited[vertex]) {

Disconnected graph with multiple components

Cycle detection runs on each component separately

DSA Javascript

for (const vertex of this.adjList.keys()) { if (!visited[vertex]) {

When to Use This Pattern

When a problem asks if a structure has loops or multiple paths, recognize it as cycle detection in graphs or trees.

Common Mistakes

Mistake: Not using a recursion stack to detect cycles in directed graphs
Fix: Use a recursion stack to track nodes in the current path to detect back edges

Mistake: Assuming all graphs are trees without checking for cycles
Fix: Always check for cycles to confirm if a graph is a tree

Summary

Shows the key difference that trees have no cycles and graphs can have cycles.

Use when you need to understand if a structure is a tree or a general graph.

The key insight is that trees are graphs without cycles and with exactly one path between 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 must be connected, but a tree can be disconnected.

Solution

1. Step 1: Understand tree structure

   A tree is a special type of graph that is connected and has no cycles.

2. Step 2: Compare with graph properties

   Graphs can have cycles and may or may not be connected.

3. Final Answer:

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

4. Quick Check:

   No cycles in tree = key difference [OK]

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

Common Mistakes:

• Thinking graphs always have a root node
• Believing trees can have cycles
• Confusing connectivity rules between graphs and trees

2. Which syntax correctly represents a tree structure in JavaScript using adjacency lists?

easy

A. const tree = [ [1, 2], [2, 3], [3, 4] ];

B. const tree = { 1: 2, 2: 3, 3: 4 };

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

D. const tree = [1, 2, 3, 4];

Solution

1. Step 1: Identify adjacency list format

   An adjacency list uses an object with keys as nodes and values as arrays of connected nodes.

2. Step 2: Check each option

   const tree = { 1: [2, 3], 2: [4], 3: [], 4: [] }; matches adjacency list format for a tree; others do not represent adjacency lists properly.

3. Final Answer:

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

4. Quick Check:

   Adjacency list uses object with arrays [OK]

Hint: Adjacency list = object keys with array values [OK]

Common Mistakes:

• Using arrays of pairs instead of adjacency lists
• Assigning single values instead of arrays for neighbors
• Confusing array of nodes with adjacency list

3. What will be the output of the following code snippet representing a graph with a cycle?

const graph = { 1: [2], 2: [3], 3: [1] };
function hasCycle(node, visited, stack) {
  if (!visited[node]) {
    visited[node] = true;
    stack[node] = true;
    for (const neighbor of graph[node]) {
      if (!visited[neighbor] && hasCycle(neighbor, visited, stack)) {
        return true;
      } else if (stack[neighbor]) {
        return true;
      }
    }
  }
  stack[node] = false;
  return false;
}
console.log(hasCycle(1, {}, {}));

medium

A. false

B. true

C. undefined

D. TypeError

Solution

1. Step 1: Understand the graph structure

   The graph has edges 1->2, 2->3, and 3->1, forming a cycle.

2. Step 2: Trace the hasCycle function

   Starting at node 1, the function detects the cycle when it revisits node 1 in the recursion stack.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Cycle detected = true [OK]

Hint: Cycle detection returns true if node revisited in recursion [OK]

Common Mistakes:

• Assuming no cycle because of simple code
• Confusing visited and recursion stack usage
• Expecting false without tracing recursion

4. Find the error in the following code that tries to check if a tree has cycles:

const tree = { 1: [2], 2: [3], 3: [] };
function hasCycle(node, visited) {
  if (visited[node]) return true;
  visited[node] = true;
  for (const neighbor of tree[node]) {
    if (hasCycle(neighbor, visited)) return true;
  }
  return false;
}
console.log(hasCycle(1, {}));

medium

A. The function does not track recursion stack, so false positives occur.

B. The visited object is not initialized properly.

C. The tree object keys should be numbers, not strings.

D. The function should return false immediately after visiting a node.

Solution

1. Step 1: Analyze cycle detection logic

   The function uses only visited to detect cycles but misses recursion stack tracking.

2. Step 2: Explain why this causes errors

   Without recursion stack, revisiting a node from a different branch may cause false cycle detection.

3. Final Answer:

   The function does not track recursion stack, so false positives occur. -> Option A

4. Quick Check:

   Missing recursion stack causes wrong cycle detection [OK]

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

Common Mistakes:

• Ignoring recursion stack importance
• Assuming visited alone detects cycles correctly
• Confusing object key types

5. Given a graph represented as adjacency lists, how can you verify if it is a tree? Choose the best approach.

hard

A. Check if the graph has cycles and is disconnected.

B. Check if the graph has no cycles regardless of connectivity.

C. Check if the graph has a root node and all nodes have at most two children.

D. Check if the graph is connected and has exactly n-1 edges for n nodes.

Solution

1. Step 1: Recall tree properties

   A tree with n nodes must be connected and have exactly n-1 edges, with no cycles.

2. Step 2: Analyze options

   Check if the graph is connected and has exactly n-1 edges for n nodes. correctly combines connectivity and edge count to verify a tree. Others miss key conditions.

3. Final Answer:

   Check if the graph is connected and has exactly n-1 edges for n nodes. -> Option D

4. Quick Check:

   Connectivity + edges = tree check [OK]

Hint: Tree = connected + edges = nodes minus one [OK]

Common Mistakes:

• Ignoring connectivity requirement
• Only checking for cycles without edges count
• Assuming root or children count defines tree