Recursive Loop for Generic Tree

Question

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:

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

You need to start by property declaring the variable in the loop: for (let i = 0; i < connections[parent].length; i++) Otherwise you are declaring a global and it's getting clobbered on recursion. — Mark
– Mark, Commented Aug 17, 2018 at 7:43
please close the question, because of the global use of i. — Nina Scholz
– Nina Scholz, Commented Aug 17, 2018 at 7:44
Thanks for editing the post @NinaScholz. After posting I was looking for how to display the images in the text. — Patrick Na
– Patrick Na, Commented Aug 17, 2018 at 7:57

CertainPerformance · Accepted Answer · 2018-08-17 07:44:27Z

5

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)

answered Aug 17, 2018 at 7:44

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Patrick Na Over a year ago

Thanks a lot for the explanation and the fix! That helps me to improve in Js.

Collectives™ on Stack Overflow

Recursive Loop for Generic Tree

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related