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



Many of the snippets in this section of the site are part of the cUseful library. You can find the details below.

https://script.google.com/macros/s/AKfycbwZ2Hht93wTNzvRmYINYF7obaOHciBXWcP_wAiEtyGq70_x3cI/exec?list=cUseful



For more like this, see  Google Apps Scripts snippets. Why not join our forum,follow the blog or follow me on twitter to ensure you get updates when they are available. 

You want to learn Google Apps Script?

Learning Apps Script, (and transitioning from VBA) are covered comprehensively in my my book, Going Gas - from VBA to Apps script, available All formats are available now from O'Reilly,Amazon and all good bookshops. You can also read a preview on O'Reilly

If you prefer Video style learning I also have two courses available. also published by O'Reilly.
Google Apps Script for Developers and Google Apps Script for Beginners.





Comments