CODEWITHSUNDEEP
javascriptrecursiondepth-first-search
Patrick Na
Patrick Na

Reputation: 119

Recursive Loop for Generic Tree

for days I am now trying to solve the following problem. A recursive function is suppose to iterate through a dictionary that is basically a representation of a tree.

The input looks like this:

var connections = {1:[2, 3, 4], 2:[5, 6, 7], 3:[8], 4:[9, 10]}

and the corresponding tree that it represents looks like this:

tree represented by the dictionary 'connections'

The intermediate goal is to print out the numbers in a depht first search manner, namely:

how the result should look like

My solution for this problem is:

function dfs(connections, parent) {
    console.log(parent);
    if (!(parent in connections)) {
      return;
    }

    for (i = 0; i < connections[parent].length; i++) {
      dfs(connections, connections[parent][i]);
    }
    return;
}

However, calling the function

dfs(connections, 1)

leads to the following result:

1
2
5
6
7

That means it is not returning to the previous function and continuing the for-loop. If you have any idea whatsoever, I would be very grateful.

Cheers

Upvotes: 2

Views: 464

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370619

Your i is implicitly global, so after it iterates through 2 (which has a length of 3), i is 4, so further tests of i < connections[parent].length fail.

You could use let to fix it (for (let i = 0), but it would probably be better to use forEach instead: array methods are less verbose, less error-prone, and more functional than for loops:

var connections = {
  1: [2, 3, 4],
  2: [5, 6, 7],
  3: [8],
  4: [9, 10]
}

function dfs(connections, parent) {
  console.log(parent);
  if (!(parent in connections)) {
    return;
  }
  connections[parent].forEach(prop => dfs(connections, prop));
}
dfs(connections, 1)

Upvotes: 5

Related Questions