Traversing a tree - Desktop Liberation

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"
                }
            ]
        }
    ]
}

{

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

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

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

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

/**

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

}

For more on snippets topic, see: