How to trace all paths of a tree like data structure?

Question

Let's say I have a nested object like so:

{
  label: 'parent',
  eyeColor: 'brown',
  kids: [
    {
      label: 'kid_0',
      eyeColor: 'brown',
      kids: [
        {
          label: 'kid_0_0',
          eyeColor: 'green',
          kids: []
        },
        {
          label: 'kid_0_1',
          eyeColor: 'brown',
          kids: [
            {
              label: 'kid_0_1_0',
              eyeColor: 'brown',
              kids: []
            }
          ]
        }
      ],
    },
    {
      label: 'kid_1',
      eyeColor: 'brown',
      kids: [
        {
          label: 'kid_1_0',
          eyeColor: 'brown',
          kids: []
        }
      ],
    },
    {
      label: 'kid_2',
      eyeColor: 'green',
      kids: []
    }
  ]
};

If I wanted to store all unique paths, how would I do so recursively? I've tried many attempts, but I can't seem to obtain unique paths (my paths build on top of previous paths).

So my expected output would be:

[
  ['parent', 'kid_0', 'kid_0_0],
  ['parent', 'kid_0', 'kid_0_1, kid_0_1_0],
  ['parent', 'kid_1', 'kid_1_0],
  ['parent', 'kid_2]
]

But if I wanted to stop the path when I found a kid or node with an eyeColor other than brown, the path would stop there. Then what would have to change to obtain the following:

[
  ['parent', 'kid_0', 'kid_0_1, kid_0_1_0],
  ['parent', 'kid_1', 'kid_1_0],
]

This is my current code, which is now error-ing out b/c of maximum call stack.

var printPaths = function(node, color) {
  var paths = [];

  var trackPath = function(obj, feature, path) {
    if (obj.eyeColor === 'brown') {
      path.push(node.label);
    } else if (obj.eyeColor !== 'brown') {
      paths.push(path);
    } else if (obj.kids.length === 0) {
      paths.push(path);
    }

    for (var i = 0; i < obj.kids.length; i++) {
      trackPath(obj.kids[i], feature, path)
      path.pop();
    }
  };

  trackPath(node, color, []);
  return paths; 
}

@Bergi I posted my broken code. I was hesitant to post it because I wanted to see how more experienced programmers approach the problem. — TheRealFakeNews, Aug 29 '16 at 01:02
That approach looks exactly fine - except that [arrays are reference values and need to be copied explicitly](http://stackoverflow.com/q/7486085/1048572). So drop the `.pop()` call and instead make the recursive call a `trackPath(obj, feature, path.slice())` — Bergi, Aug 29 '16 at 01:07
@Bergi do you mean `obj.kids[i]`? I added the `.slice()`, but then I just get `[ [ 'parent', 'parent' ], [ 'parent', 'parent', 'parent' ], [ 'parent', 'parent' ] ]`. It doesn't do as I expect. — TheRealFakeNews, Aug 29 '16 at 01:10
No, I mean the `path`. It's referring to the exact same array everywhere, to the array you created in the initial `trackPath(node, color, []);` call. — Bergi, Aug 29 '16 at 01:14
Btw, the `obj.kids.length === 0` path is never taken. The eyecolor always already is brown or not brown. — Bergi, Aug 29 '16 at 01:15
@Bergi Yeah, regarding that, I posted an example that didn't cover all cases, but the idea is that when it reaches the end of a path or when it encounters a non-brown eye color, it would push that path to `paths` — TheRealFakeNews, Aug 29 '16 at 01:16
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/122060/discussion-between-alanh-and-bergi). — TheRealFakeNews, Aug 29 '16 at 01:18
@AlanH but shouldn't the path stop at "parent"? because "parent" already has a child with an eyeColor other than green. — Thomas, Aug 29 '16 at 02:21

score 1 · Accepted Answer · edited May 23 '17 at 12:16

Your approach is mostly fine, the only problem was that assignment or argument passing doesn't copy arrays. Introduce a slice() call into the recursion:

function printPaths(node, color) {
  var paths = [];

  function trackPath(obj, feature, path) {
    if (obj.eyeColor !== feature) { // found target
      paths.push(path);
      return;
    } // else continue
    path.push(obj.label);

    for (var i = 0; i < obj.kids.length; i++) {
      trackPath(obj.kids[i], feature, path.slice());
//                                        ^^^^^^^^
    }
  }

  trackPath(node, color, []);
  return paths;
}

@AlanH: The `feature` thing was different, after my edit it should behave identical to your answer — Bergi, Aug 29 '16 at 17:53

score 0 · Answer 2 · answered Aug 29 '16 at 02:14

here is my approach, I had to rewrite your logic as well as use array copying using slice

var printPaths = function(node, color) {
  var paths = [];

  var trackPath = function(obj, feature, path) {
    //debugger;
    path.push(obj.label);

    if (obj.eyeColor === 'brown') {
      if (obj.kids.length == 0) {
        paths.push(path.slice());
      }
      else {
        for (var i = 0; i < obj.kids.length; i++) {
          trackPath(obj.kids[i], feature, path);
        }
      }
    } 


    path.pop();
  };

  trackPath(node, color, []);
  return paths; 
}

score 0 · Answer 3 · answered Aug 29 '16 at 17:22

This was the solution that I ended up getting to work. I had help from @Bergi, but his solution doesn't quite do what I need. This solution pasts all the tests I wrote.

var printPaths = function(node, color) {
  var paths = [];

  var trackPath = function(obj, feature, path) {    
    // if the current node has the desired property, push that
    // to the current path, then continue checking checking
    // if there are any children (two if statements down)
    if (obj.eyeColor === feature) {
      path.push(obj.label);
    } 
    // if we encounter a path that isn't our desired property,
    // don't push the current node on to the current path, but instead
    // just push the failed path, and return, so that it doesn't
    // continue to check
    if (obj.eyeColor !== feature) {
      paths.push(path);
      return;
    }
    // if we're at a leaf node, i.e we had a full successful path
    // (everyone had brown eyes)
    if (obj.kids.length === 0) {
      paths.push(path);
    }

    for (var i = 0; i < obj.kids.length; i++) {
      trackPath(obj.kids[i], feature, path.slice())
    }
  };

  trackPath(node, color, []);
  return paths; 
}

How to trace all paths of a tree like data structure?

3 Answers3