Why Graphs Exist and What Trees Cannot Model in DSA Typescript - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a graph node with a list of neighbors.

DSA Typescript

class GraphNode {
  value: number;
  neighbors: GraphNode[];
  constructor(value: number) {
    this.value = value;
    this.neighbors = [1];
  }
}

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

A[]

B{}

Cnull

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using {} which creates an object instead of an array.

Setting neighbors to null or 0 which are not lists.

The neighbors list should be initialized as an empty array to hold connected nodes.

2fill in blank

medium

Complete the code to add an edge between two graph nodes.

DSA Typescript

function addEdge(node1: GraphNode, node2: GraphNode) {
  node1.neighbors.[1](node2);
  node2.neighbors.push(node1);
}

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

Aappend

Binsert

Cadd

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using append which is not a method on arrays in TypeScript.

Using add or insert which are not valid array methods.

The push method adds an element to the end of an array in TypeScript.

3fill in blank

hard

Fix the error in the code to check if a graph has a cycle.

DSA Typescript

function hasCycle(node: GraphNode, visited: Set<number>): boolean {
  if (visited.has(node.value)) {
    return [1];
  }
  visited.add(node.value);
  for (const neighbor of node.neighbors) {
    if (hasCycle(neighbor, visited)) {
      return true;
    }
  }
  return false;
}

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

Afalse

Btrue

Cnull

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Returning false which means no cycle found incorrectly.

Returning null or undefined which are not boolean values.

If the node was already visited, it means a cycle exists, so return true.

4fill in blank

hard

Fill both blanks to create an adjacency list representation of a graph.

DSA Typescript

const graph: [1] = {};
function addEdge(u: number, v: number) {
  if (!graph[u]) graph[u] = [2];
  graph[u].push(v);
}

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

ARecord<number, number[]>

BArray<number>

C[]

D{}

Attempts:

3 left

💡 Hint

Common Mistakes

Using {} for adjacency lists which is an object, not an array.

Using Array as the graph type which is incorrect.

The graph is a record mapping numbers to arrays of numbers. Initialize empty arrays for adjacency lists.

5fill in blank

hard

Fill all three blanks to implement a breadth-first search (BFS) on a graph.

DSA Typescript

function bfs(start: number, graph: Record<number, number[]>): number[] {
  const visited = new Set<number>();
  const queue: number[] = [start];
  const result: number[] = [];
  while (queue.length > 0) {
    const node = queue.[1]();
    if (!visited.has(node)) {
      visited.add(node);
      result.push(node);
      for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
          queue.[2](neighbor);
        }
      }
    }
  }
  return [3];
}

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

Ashift

Bpush

Cresult

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() which removes from the end, causing DFS behavior.

Returning queue instead of the result list.

Use shift() to dequeue from the front, push() to enqueue neighbors, and return the result list.

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