DFS Depth First Search on Graph in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

DFS traversal order on a simple graph

What is the output order of nodes visited by the DFS starting from node 'A'?

DSA Javascript

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

function dfs(graph, start) {
  const visited = new Set();
  const result = [];

  function traverse(node) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph[node]) {
      traverse(neighbor);
    }
  }

  traverse(start);
  return result;
}

console.log(dfs(graph, 'A'));

A ["A", "B", "D", "C", "E"]

B ["A", "B", "C", "D", "E"]

C ["A", "C", "E", "B", "D"]

D ["A", "D", "B", "C", "E"]

💡 Hint

Remember DFS explores as far as possible along each branch before backtracking.

Starting at 'A', DFS visits 'B' first, then 'D' (no neighbors), backtracks to 'A', then visits 'C' and 'E'.

❓ Predict Output

intermediate

DFS on graph with cycle detection

What is the output of the DFS traversal starting from node 1 on this graph with a cycle?

DSA Javascript

const graph = {
  1: [2, 3],
  2: [4],
  3: [2],
  4: [1]
};

function dfs(graph, start) {
  const visited = new Set();
  const result = [];

  function traverse(node) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph[node]) {
      traverse(neighbor);
    }
  }

  traverse(start);
  return result;
}

console.log(dfs(graph, 1));

A [1, 3, 2, 4]

B [1, 2, 4, 3]

C [1, 2, 3, 4]

D [1, 4, 2, 3]

💡 Hint

DFS should not revisit nodes already visited, even if cycles exist.

DFS visits 1, then 2, then 4. From 4, it tries to visit 1 but skips since visited. Then backtracks and visits 3.

🔧 Debug

advanced

Identify the error in DFS implementation

What error will this DFS code produce when run on the given graph?

DSA Javascript

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

function dfs(graph, start) {
  const visited = new Set();
  const result = [];

  function traverse(node) {
    if (visited.has(node)) return;
    result.push(node);
    for (const neighbor of graph[node]) {
      traverse(neighbor);
    }
    visited.add(node);
  }

  traverse(start);
  return result;
}

console.log(dfs(graph, 'A'));

A Stack overflow due to infinite recursion

B Empty array []

C ["A", "B", "C"]

D TypeError: Cannot read property of undefined

💡 Hint

Check when nodes are marked visited in the recursion.

The visited set is updated after recursion, so nodes are revisited causing infinite recursion and stack overflow.

❓ Predict Output

advanced

DFS traversal on disconnected graph

What is the output of DFS starting from node 'X' on this disconnected graph?

DSA Javascript

const graph = {
  X: ['Y'],
  Y: [],
  Z: ['W'],
  W: []
};

function dfs(graph, start) {
  const visited = new Set();
  const result = [];

  function traverse(node) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph[node]) {
      traverse(neighbor);
    }
  }

  traverse(start);
  return result;
}

console.log(dfs(graph, 'X'));

A ["Y", "X"]

B ["X", "Y", "Z", "W"]

C ["X", "Y"]

D ["Z", "W"]

💡 Hint

DFS only visits nodes reachable from the start node.

Starting at 'X', DFS visits 'Y'. Nodes 'Z' and 'W' are disconnected and not visited.

❓ Predict Output

expert

DFS with stack instead of recursion

What is the output of this iterative DFS starting from node 1?

DSA Javascript

const graph = {
  1: [2, 3],
  2: [4],
  3: [5],
  4: [],
  5: []
};

function dfsIterative(graph, start) {
  const stack = [start];
  const visited = new Set();
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited.has(node)) {
      visited.add(node);
      result.push(node);
      for (let i = graph[node].length - 1; i >= 0; i--) {
        stack.push(graph[node][i]);
      }
    }
  }
  return result;
}

console.log(dfsIterative(graph, 1));

A [1, 3, 5, 2, 4]

B [1, 4, 2, 5, 3]

C [1, 2, 3, 4, 5]

D [1, 2, 4, 3, 5]

💡 Hint

Stack LIFO order affects traversal order; neighbors are pushed in reverse order.

Stack causes DFS to visit 1, then 2, then 4, backtrack to 3, then 5.

Practice

1. What does DFS (Depth First Search) do when traversing a graph?

easy

A. It only visits nodes connected directly to the start node.

B. It visits nodes level by level from the start node.

C. It explores as far as possible along each branch before backtracking.

D. It randomly visits nodes without any order.

Solution

1. Step 1: Understand DFS traversal

   DFS explores a path deeply before moving to another path.

2. Step 2: Compare with other traversals

   BFS visits nodes level by level, but DFS goes deep first.

3. Final Answer:

   It explores as far as possible along each branch before backtracking. -> Option C

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS goes deep first, BFS goes wide first [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits nodes randomly
• Assuming DFS only visits direct neighbors

2. Which of the following is the correct way to start a DFS function in JavaScript for a graph represented as adjacency list graph?

easy

A. function dfs(node, visited = new Set()) {

B. function dfs(node, visited = []) {

C. function dfs(node, visited = {}) {

D. function dfs(node, visited = 0) {

Solution

1. Step 1: Identify suitable data structure for visited nodes

   A Set is ideal to track visited nodes efficiently.

2. Step 2: Check function signature correctness

   Using visited = new Set() initializes visited nodes properly.

3. Final Answer:

   function dfs(node, visited = new Set()) { -> Option A

4. Quick Check:

   Use Set for visited nodes [OK]

Hint: Use Set to track visited nodes in DFS [OK]

Common Mistakes:

• Using array or object incorrectly for visited
• Initializing visited as a number
• Not initializing visited parameter

3. Given the graph adjacency list:

const graph = {
  1: [2, 3],
  2: [4],
  3: [],
  4: []
};

function dfs(node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited);
    }
  }
  return Array.from(visited);
}

console.log(dfs(1));

What is the output?

medium

A. [1, 3, 2, 4]

B. [1, 4, 2, 3]

C. [1, 2, 3, 4]

D. [1, 2, 4, 3]

Solution

1. Step 1: Start DFS from node 1

   Visit 1, then neighbors 2 and 3 in order.

2. Step 2: Visit neighbors recursively

   From 2, visit 4. From 3, no neighbors. Order: 1, 2, 4, 3.

3. Final Answer:

   [1, 2, 4, 3] -> Option D

4. Quick Check:

   DFS order = 1,2,4,3 [OK]

Hint: Follow neighbors deeply before next sibling [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Confusing BFS order with DFS
• Not converting Set to array properly

4. Find the error in this DFS code snippet for graph traversal:

const graph = {
  1: [2, 3],
  2: [4],
  3: [],
  4: []
};

function dfs(node, visited = new Set()) {
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (visited.has(neighbor)) {
      dfs(neighbor, visited);
    }
  }
  return visited;
}

console.log(Array.from(dfs(1)));

medium

A. The condition should be if (!visited.has(neighbor)) instead of if (visited.has(neighbor))

B. The visited set should be an array instead

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

D. The function should return an array, not a set

Solution

1. Step 1: Check the neighbor visit condition

   It incorrectly calls dfs if neighbor is already visited, causing infinite recursion.

2. Step 2: Correct the condition

   Change to if (!visited.has(neighbor)) to visit unvisited neighbors only.

3. Final Answer:

   The condition should be if (!visited.has(neighbor)) instead of if (visited.has(neighbor)) -> Option A

4. Quick Check:

   Visit only unvisited neighbors [OK]

Hint: Call DFS only if neighbor not visited [OK]

Common Mistakes:

• Calling DFS on already visited nodes
• Using wrong data structure for visited
• Returning wrong type from DFS

5. You want to find if there is a path from node 1 to node 5 in this graph:

const graph = {
  1: [2, 3],
  2: [4],
  3: [5],
  4: [],
  5: []
};

function dfs(node, target, visited = new Set()) {
  if (node === target) return true;
  visited.add(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      if (dfs(neighbor, target, visited)) return true;
    }
  }
  return false;
}

console.log(dfs(1, 5));

What will be the output and why?

hard

A. false, because the visited set is not updated correctly

B. true, because DFS finds a path 1 -> 3 -> 5

C. true, because DFS visits all nodes regardless of target

D. false, because node 5 is not directly connected to 1

Solution

1. Step 1: Check DFS path search logic

   DFS returns true immediately when target node is found.

2. Step 2: Trace path from 1 to 5

   Path exists: 1 -> 3 -> 5, so DFS returns true.

3. Final Answer:

   true, because DFS finds a path 1 -> 3 -> 5 -> Option B

4. Quick Check:

   DFS finds path = true [OK]

Hint: DFS returns true when target found [OK]

Common Mistakes:

• Assuming direct connection needed
• Ignoring early return on target found
• Not updating visited set properly