Job interview question : recursion

Your most recent code isn’t really breadth first or depth first. It only works with a depth of 1.

thanks, Ill go over these later

no clue what your talking about, I made it deeper, its working as expected.

I made a mistake before, the console prints them out in a condensed array, the debugger shows it clearly looks like breath search

@DanCouper is right it does look like breath first search, each one level by level is my understanding of that

No, what I’m describing visits each node at the first level under the root (Menu1, Menu3). The it wisits each node at the second level (Menu2, Menu4). Then each node at the third level (Menu5, Menu6)

root -->
            |------|
lvl1 --> menu1    menu3
            |        |
lvl2 --> menu2    menu4
                 |----|
lvl3 -->     menu5    menu6
1 Like

Yes I know, I made a miatake, that which you described is exactly what the code is doing for me

??? I made it deeper there are two objects in the items array the first time the rest is children. it gets all of them as expected. how you can say it only works with a depth of 1?

W/r/t the original code, which didn’t go past one level of the tree, not after you fixed it

How? I tried:

const processForEach = (items, names = []) => {
  items.forEach(function (elem) {
    names.push(elem.name);
    if (elem.subitems) {
      this.push(...elem.subitems);
    }
  }, items);

  // items.forEach((elem) => {
  //   names.push(elem.name);
  //   if (elem.subitems) {
  //     items.push(...elem.subitems);
  //   }
  // });
  return names;
};

doesnt work

I’m saying use an explicit loop, not fanny on trying to make forEach work.

Yes, I understood that, but if I wanted to make it work, for research/learning purposes, how would I do it?

You clarified before:

const processStandard = (items, names = []) => {
  for (let i = 0; i < items.length; i++) {
    names.push(items[i].name);
    if (items[i].subitems) {
      items.push(...items[i].subitems);
    }
  }
  return names;
};

forEach is fundamentally not designed to work the way you would need for breadth first.

You’ve gone back to making this a depth 1 search, so its not really either a breadth first or a depth first… I really recommend trying the two challenges I linked.

2 Likes

Well, you need to know the length of the array before you start, and, critically, what the values are, so its chicken and egg

forEach() calls a provided callbackFn function once for each element in an array in ascending index order. It is not invoked for index properties that have been deleted or are uninitialized [emphasis mine]

The items you add to the array during iteration are uninitialized when you define it, ipso facto the callback won’t run for them. So, conversely, if you wanted to stop when some condition was met, you can short circuit any of the array methods by deleting everything in an array past a certain point during iteration. But adding things to the array isn’t going to do anything. It’s the wrong tool for doing this

1 Like