DFS traversal and applications in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start a DFS traversal from the given node.

Data Structures Theory

def dfs(node, visited):
    if node is None or node in visited:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs([1], visited)

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

Anode

BNone

Cvisited

Dneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Calling dfs on the current node again causes infinite recursion.

Passing visited instead of the next node.

In DFS, we recursively visit each neighbor of the current node. So, the recursive call should be on neighbor.

2fill in blank

medium

Complete the code to mark a node as visited in DFS.

Data Structures Theory

def dfs(node, visited):
    if node is None or node in visited:
        return
    [1].add(node)
    for neighbor in node.neighbors:
        dfs(neighbor, visited)

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

Aneighbor

Bnode

Cvisited

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the neighbor instead of the current node.

Trying to add to the node instead of the visited set.

We add the current node to the visited set to mark it as visited and avoid revisiting it.

3fill in blank

hard

Fix the error in the DFS code to avoid revisiting nodes.

Data Structures Theory

def dfs(node, visited):
    if node is None or [1]:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs(neighbor, visited)

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

Anode in visited

Bnode not in visited

Cneighbor in visited

Dneighbor not in visited

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if node is not in visited causes infinite recursion.

Checking neighbors instead of the current node.

The condition should check if the current node is already in visited to stop revisiting it.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps nodes to their depth in DFS.

Data Structures Theory

def dfs_depth(node, depth, depths, visited):
    if node is None or node in visited:
        return
    visited.add(node)
    depths[node] = depth
    for neighbor in node.neighbors:
        dfs_depth(neighbor, depth [1] 1, depths, visited)

result = {node: depths[node] for node in depths if depths[node] [2] 2}

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

A+

B-

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition for depth.

Using wrong comparison operator for filtering.

We increase depth by 1 when going deeper in DFS, so use +. To filter nodes deeper than 2, use >.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps nodes to their neighbors if the neighbor is unvisited.

Data Structures Theory

def dfs_neighbors(node, visited):
    return {neighbor: node for neighbor in node.neighbors if neighbor not in [1]

visited = set()
result = dfs_neighbors([2], visited)
visited.add([3])

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

Avisited

Bnode

Cneighbor

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Using neighbor instead of visited for the check.

Adding neighbor instead of node to visited.

The comprehension checks neighbors not in visited. We call the function on node and add node to visited.