A common pattern is traversing a tree, and you find yourself writing the same recursive code over an over. Although it’s a very simple problem, people often have trouble with it. Here’s a general pattern you can use.
Let’s say you have some data that looks like this – a classic tree structure.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
{ "name": "Granddad", "children": [ { "name": "dad", "children": [ { "name": "me" }, { "name": "lucy" } ] }, { "name": "uncle bob", "children": [ { "name": "cousin hank" } ] } ] } |
1 2 3 4 5 6 7 8 |
traverseTree (tree, function (node,depth) { // do some processing with each node }, function (parent) { // explain how to get the children of a given parent } ); |
1 2 3 4 5 6 7 8 |
traverseTree (tree, function (node,depth) { Logger.log(node.name + ":depth " + depth); }, function (parent) { return parent.children; } ); |
1 2 3 4 5 6 |
[15-05-07 10:03:57:059 BST] Granddad:depth 0 [15-05-07 10:03:57:060 BST] dad:depth 1 [15-05-07 10:03:57:060 BST] me:depth 2 [15-05-07 10:03:57:060 BST] lucy:depth 2 [15-05-07 10:03:57:061 BST] uncle bob:depth 1 [15-05-07 10:03:57:061 BST] cousin hank:depth 2 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/** * general function to walk through a branch * @param {object} parent the head of the branch * @param {function} nodeFunction what to do with the node * @param {function} getChildrenFunctiontion how to get the children * @param {number} depth optional depth of node * @return {object} the parent for chaining */ function traverseTree (parent, nodeFunction, getChildrenFunction, depth) { depth = depth || 0; // if still some to do if (parent) { // do something with the header nodeFunction (parent, depth++); // process the children (getChildrenFunction(parent) || []).forEach ( function (d) { traverseTree (d , nodeFunction , getChildrenFunction, depth); }); } return parent; } |