recursively stepping through a Javascript object

Question

I am trying to learn to recursively step through a javascript object. To be more specific, I am doing the recursion problem for functional javascript is good on nodeschool.io. My code is not recursing properly and I can't figure out why.

This is my code so far:

module.exports = function getDependencies (tree) {
    var arr = [];

    function findKeys(branch) {
        var branchHolder = [];

        branchHolder = branchHolder.concat(Object.keys(branch));
        //console.log(branchHolder);
        var filtered = branchHolder.filter(function (value) {
            return value !== 'name' && value !== 'version';
        })
        console.log(filtered);
        filtered.forEach(function (twig) {
            if (typeof branch[twig] === 'object' && twig === 'dependencies') {
                //console.log(twig);
                findKeys(branch[twig]);
            } else {
                //console.log(branch[twig]);
                arr.push(twig + '@' + branch[twig].version);
                //console.log(arr);
            }


            /*
            //if (branch[twig]) {console.log(branch[twig])}
            if (twig !== 'dependencies') {
                arr.push(twig + '@' + branch[twig].version)
                //console.log(arr)
            } else if (typeof branch[twig] === 'object') {
                //console.log(branch[twig]);
                findKeys(branch[twig]);
            }
            */
        })
    }

    findKeys(tree);
    return arr.sort();
}

For some reason, my code isn't working. I tested a bare bones version of the code and it seems to work.

function traverse(o) {
    if (typeof o === 'object') {
        for (var key in o) {
            console.log('key: ', key);
            traverse(o[key]);
        }
    } else {
        console.log(o);
    }
}

a = {foo: 'bar', baz: 'quux', zot: [1, 2, 3, {some: 'hash'}]}

traverse(a)

Can someone tell me what is different between these two blocks of code?

Thank you in advance. :)

Andrew

something that looks a little like this: var loremIpsum = { "name": "lorem-ipsum", "version": "0.1.1", "dependencies": { "optimist": { "version": "0.3.7", "dependencies": { "wordwrap": { "version": "0.0.2" } } }, "inflection": { "version": "1.2.6" } } } — ajw650, Mar 16 '16 at 19:06
I am just differentiating from other objects like xml objects. — ajw650, Mar 16 '16 at 19:09
JSON is a string format that represents data like objects and arrays in a convenient way, just like xml format. Here you have a Javascrip Object, this has still nothing to do with JSON — RaphBlanchet, Mar 16 '16 at 19:11
What is the difference between Javascript Object and JSON(Javascript Object Notation)? — ajw650, Mar 16 '16 at 19:13
JSON is a NOTATION, which means it can represents every type of javascript objects in a simple string. A JSON is a string representation of your objects, which was created at first for javascript, but now used in almost every single programmation language because of its simplicity. — RaphBlanchet, Mar 16 '16 at 19:19
where are you defining tree? What does the input to this function look like? What is it doing instead of recursing? — linuxdan, Mar 16 '16 at 19:25

score 0 · Accepted Answer · answered Mar 16 '16 at 19:36

Look closely at the structure of your recursive if:

if (typeof branch[twig] === 'object' && twig === 'dependencies') {
  findKeys(branch[twig]);
}

You iterate over the keys of your object, and only recurse on keys that are dependencies which go to objects. Then you only save things that don't meet this requirement.

Now look at the structure of your data:

var loremIpsum = {
  "name": "lorem-ipsum",
  "version": "0.1.1",
  "dependencies": {
    "optimist": {
      "version": "0.3.7",
      "dependencies": {
        "wordwrap": {
          "version": "0.0.2"
        }
      }
    },
    "inflection": {
      "version": "1.2.6"
    }
  }
}

Your top-level object has three keys: name, version, and dependencies. You filter out name and version and recurse on your dependencies. Great! Now, your recursive object looks like:

{
  "optimist": {
     version": "0.3.7",
    "dependencies": {
      "wordwrap": {
        "version": "0.0.2"
      }
    }
  },
  "inflection": {
    "version": "1.2.6"
  }
}

So you save the names and versions of optimist and inflection ... but then you don't recurse! Because the keys here are "optimist" and "inflection", not "dependencies".

The core problem here is that you WANT to recurse when your recursive object has a "dependencies" key, but you're not looking deep enough. It seems like you are slightly confused as to the exact structure of your various recursive objects at every point.

You probably want a recursive case that looks a little more like this:

if (typeof branch[twig] === 'object') {
  arr.push(twig + '@' + branch[twig].version);
  if (branch[twig].dependencies) {
    findKeys(branch[twig].dependencies);
  }
}

function getDependencies(tree) {
  var arr = [];

  function findKeys(branch) {
    var branches = Object.keys(branch).filter(function(value) {
      return value !== 'name' && value !== 'version';
    })
    branches.forEach(function(twig) {
      if (typeof branch[twig] === 'object') {
        arr.push(twig + '@' + branch[twig].version);
        if (branch[twig].dependencies) {
          findKeys(branch[twig].dependencies);
        }
      }
    })
  }

  findKeys(tree);
  return arr.sort();
}

var loremIpsum = {
  "name": "lorem-ipsum",
  "version": "0.1.1",
  "dependencies": {
    "optimist": {
      "version": "0.3.7",
      "dependencies": {
        "wordwrap": {
          "version": "0.0.2"
        }
      }
    },
    "inflection": {
      "version": "1.2.6"
    }
  }
}

deps = getDependencies(loremIpsum.dependencies)
document.write(JSON.stringify(deps))

recursively stepping through a Javascript object

1 Answers1