Why Graphs Exist and What Trees Cannot Model in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why can't trees model all relationships?

Which of the following scenarios cannot be accurately represented by a tree structure?

A A family tree showing parent-child relationships

B A company's organizational chart with one manager per employee

C A social network where people can be friends with multiple others

D A file system directory with folders and subfolders

💡 Hint

Think about whether each node can have multiple parents or connections.

Trees have a strict hierarchy where each node has only one parent. Social networks allow multiple connections between nodes, which trees cannot represent.

❓ Predict Output

intermediate

Output of graph adjacency list vs tree adjacency list

Given the following adjacency lists, which one represents a graph that cannot be a tree?

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};

DSA Typescript

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};

console.log(graph);

A {"A":["B","C"],"B":["A"],"C":["A"],"D":["B"]}

B {"A":["B","C"],"B":["D"],"C":["A"],"D":[]}

C {"A":["B"],"B":["C"],"C":["D"],"D":[]}

D {"A":["B","C"],"B":["A","D"],"C":["A","D"],"D":["B","C"]}

💡 Hint

Look for cycles or multiple parents in the adjacency list.

Option D shows nodes connected in a cycle (A-B-D-C-A), which trees cannot have.

🔧 Debug

advanced

Identify the error in tree vs graph edge representation

Which option shows an incorrect edge representation for a tree structure?

Edges:
A - B
B - C
C - A

A Edges form a cycle: A-B, B-C, C-A, which is invalid for trees

B Edges form a linear chain: A-B, B-C, which is valid for trees

C Edges form a star: A-B, A-C, which is valid for trees

D Edges form disconnected nodes: A-B, C-D, which is valid for trees

💡 Hint

Trees cannot have cycles.

Option A forms a cycle, which violates the tree property of having no cycles.

🚀 Application

advanced

Choosing graph over tree for modeling

You want to model a city's road network where intersections connect multiple roads in various ways. Which data structure is best?

A Tree, because roads branch out from a central point

B Graph, because intersections can connect multiple roads forming cycles

C Linked list, because roads are linear

D Stack, because roads can be traversed in order

💡 Hint

Think about whether the structure allows cycles and multiple connections.

Graphs allow cycles and multiple connections, which fits road networks better than trees.

🧠 Conceptual

expert

Why graphs are necessary beyond trees

Which property of graphs makes them necessary to model relationships that trees cannot?

A Graphs allow multiple parents per node and cycles, unlike trees

B Graphs enforce a strict hierarchy with no cycles

C Graphs only allow one path between nodes

D Graphs are always directed and acyclic

💡 Hint

Consider the flexibility of connections in graphs vs trees.

Graphs can have cycles and nodes with multiple parents, which trees cannot, making graphs more flexible for complex relationships.

Practice

1. Why do we need graphs when we already have trees in data structures?

easy

A. Because trees can only store numbers, not other data types.

B. Because trees are faster to traverse than graphs.

C. Because graphs are simpler and have no edges.

D. Because graphs can represent connections between nodes in any pattern, including cycles.

Solution

1. Step 1: Understand tree limitations

   Trees are hierarchical and cannot have cycles or multiple parents for a node.

2. Step 2: Understand graph capabilities

   Graphs allow any connections, including cycles and multiple edges between nodes.

3. Final Answer:

   Because graphs can represent connections between nodes in any pattern, including cycles. -> Option D

4. Quick Check:

   Graphs model cycles, trees cannot [OK]

Hint: Graphs allow cycles; trees do not [OK]

Common Mistakes:

• Thinking trees can have cycles
• Confusing data types with structure
• Assuming graphs are simpler than trees

2. Which of the following is the correct way to declare an adjacency list for a graph in TypeScript?

easy

A. const graph: number = [];

B. const graph: number[][] = [];

C. const graph: string = {};

D. const graph: boolean[] = {};

Solution

1. Step 1: Identify adjacency list type

   An adjacency list is an array of arrays, where each inner array holds connected node indices.

2. Step 2: Match TypeScript syntax

   TypeScript syntax for adjacency list is number[][] for array of number arrays.

3. Final Answer:

   const graph: number[][] = []; -> Option B

4. Quick Check:

   Adjacency list = number[][] [OK]

Hint: Adjacency list is array of arrays [OK]

Common Mistakes:

• Using single number type for adjacency list
• Using object {} instead of array []
• Wrong type annotations

3. Consider the following TypeScript code representing a graph with cycles:

const graph: number[][] = [[1], [2], [0]];
function hasCycle(node: number, visited: boolean[], stack: boolean[]): boolean {
  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;
}
const visited = [false, false, false];
const stack = [false, false, false];
console.log(hasCycle(0, visited, stack));

What is the output?

medium

A. Runtime error

B. false

C. true

D. undefined

Solution

1. Step 1: Understand graph structure

   Graph edges: 0->1, 1->2, 2->0 form a cycle.

2. Step 2: Trace hasCycle function

   DFS visits nodes 0,1,2 and detects back edge from 2 to 0 in recursion stack, returning true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Cycle detected = true [OK]

Hint: Cycle detection returns true if back edge found [OK]

Common Mistakes:

• Assuming no cycle in small graph
• Confusing visited and stack arrays
• Ignoring recursion stack usage

4. The following TypeScript code attempts to detect cycles in a graph but has a bug:

const graph: number[][] = [[1], [2], [0]];
function hasCycle(node: number, visited: boolean[], stack: boolean[]): boolean {
  if (visited[node]) {
    return false;
  }
  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;
}
const visited = [false, false, false];
const stack = [false, false, false];
console.log(hasCycle(0, visited, stack));

What is the bug in this code?

medium

A. It returns false immediately if node is visited, missing cycles.

B. It never marks nodes as visited.

C. It uses wrong data types for visited and stack arrays.

D. It does not check neighbors of the node.

Solution

1. Step 1: Analyze early return on visited node

   Returning false immediately when node is visited skips cycle detection on back edges.

2. Step 2: Understand correct cycle detection logic

   Should only return false if node visited and not in recursion stack; else return true if in stack.

3. Final Answer:

   It returns false immediately if node is visited, missing cycles. -> Option A

4. Quick Check:

   Early return on visited node causes missed cycles [OK]

Hint: Do not return false immediately on visited node [OK]

Common Mistakes:

• Returning false too early
• Confusing visited and recursion stack
• Ignoring recursion stack check

5. You want to model a social network where users can follow each other in any pattern, including mutual follows and cycles. Which data structure best models this, and why can't a tree be used?

hard

A. Use a graph because it supports cycles and multiple connections; trees cannot model cycles or multiple parents.

B. Use a tree because it is simpler and supports cycles naturally.

C. Use a linked list because it models one-way connections well.

D. Use an array because it stores all users efficiently.

Solution

1. Step 1: Identify social network connection patterns

   Users can follow each other in any pattern, including cycles and mutual connections.

2. Step 2: Compare data structures

   Trees cannot represent cycles or multiple parents; graphs can represent any connection pattern.

3. Final Answer:

   Use a graph because it supports cycles and multiple connections; trees cannot model cycles or multiple parents. -> Option A

4. Quick Check:

   Graphs model social networks; trees cannot [OK]

Hint: Social networks need graphs for cycles and mutual links [OK]

Common Mistakes:

• Choosing tree for cyclic connections
• Confusing linked list with graph
• Ignoring cycles in social networks