Traversing a tree

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.

{
    "name": "Granddad",
    "children": [
        {
            "name": "dad",
            "children": [
                {
                    "name": "me"
                },
                {
                    "name": "lucy"
                }
            ]
        },
        {
            "name": "uncle bob",
            "children": [
                {
                    "name": "cousin hank"
                }
            ]
        }
    ]
}

Typically you want to traverse this and do something at each node – using a pattern like this we can generalize …

 traverseTree (tree,
    function (node,depth) {
      // do some processing with each node
    },
    function (parent) {
      // explain how to get the children of a given parent
    }
  );

So in the case of our data we want to just log the name and depth of each tree node

traverseTree (tree,
    function (node,depth) {
      Logger.log(node.name + ":depth " + depth);
    },
    function (parent) {
      return parent.children;
    }
  );

which gives this result

[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

Here’s the traverseTree function, which you can copy from here or use directly from the cUseful library.

/**
* 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;
}