In JavaScript recursion primer I introduced a simple example to show how recursion works. We are going to develop some of those ideas in this post, so you should first read that.
We’ll use the same object as in JavaScript recursion primer , but this time we’ll focus on node parents , rather than node children. So we’ll be using the concept of a node parent to be able to travel back up a tree, or to identify siblings (other nodes with the same parents).
Adding parent links
In the primer example, we created a structure like this for each node.
var node = { "label":"im a node", "children":[]};
Now we need to add a parent to each node, so it will look like this.
var node = { "label":"im a node", "children":[], parent:null};
Parent links can’t be added in JSON since we need to add object pointers, but we can use what we learned about traversing a tree via children links to add the parents.
Since we’ll be doing this a few times, we’ll create a function out of it. You should be able to figure out what’s going on here – every child node of the passed parent is stamped with a pointer to that parent, then the function is called recursively by each node so that its children can also record their parent – and so on….
function addParentLinks (parent) {
// add a parent link to a child structure
parent.children.forEach(function(d) {
// each child gets marked with a parent
d.parent = parent;
// then marks its own children with itself
addParentLinks(d);
});
return parent;
}
and we call it like this, passing the root of the tree we created in JavaScript recursion primer.
var tree = addParentLinks(root);
Identifying siblings
Now that our tree structure is stamped with both children and parent links, from any node we can find its parents, grandparents and so on. We can also find its siblings – nodes with the same parents.
A minor change to the print function used in JavaScript recursion primer will show a node’s siblings in the log. First though we’ll move the indent function from within the previous print function to be accessible from this function too, since we’ll use that for formatting the output.
function indent(by,pad) {
// if there is any indentation to do, create a and array of requested length and use pad character to join
return by > 0 ? new Array(by+1).join(pad) : "";
}
Here’s the updated version.
function traverseParents() {
// demo to show how to traverse a parent/child two way link structure
// first add parent links
var tree = addParentLinks(root);
// now go through printing the structure, but show siblings using the parent
recursiveSiblings (tree);
function recursiveSiblings(node,depth) {
// if we didnt get a depth, start at 0
depth = depth || 0;
// indent by double the node depth
var text = indent(depth*2 , "-") + node.label;
// show any siblings
if (node.parent && node.parent.children.length > 1) {
// this will list any nodes with the same parent who is not the current node
Logger.log(text + ' (My sibling' + (node.parent.children.length > 2 ? 's are ' : ' is ') +
node.parent.children.filter(function(d) {
return d !== node;
})
.map(function(d) {
return d.label;
})
.join(",")+')');
}
else {
Logger.log(text + ' (I have no siblings) ');
}
// indent the children a bit more
depth++;
// process the children
node.children.forEach(function(childNode) {
recursiveSiblings (childNode,depth);
});
// unindent as we're finished the children
depth--;
}
}
and the result …
Note that each node now also shows its sibling(s) in brackets
[15-02-05 10:43:29:726 GMT] There are 2 kinds of people in the world (I have no siblings) [15-02-05 10:43:29:727 GMT] --Those that get recursion (My sibling is Those that don't) [15-02-05 10:43:29:727 GMT] ----ahmed (My sibling is zoe) [15-02-05 10:43:29:728 GMT] ----zoe (My sibling is ahmed) [15-02-05 10:43:29:728 GMT] --Those that don't (My sibling is Those that get recursion) [15-02-05 10:43:29:729 GMT] ----Those that could learn (My sibling is Those that never will) [15-02-05 10:43:29:729 GMT] ------Those that just need a little practise for the lightbulb to go off (My sibling is Those that need coaching) [15-02-05 10:43:29:729 GMT] --------mike (My sibling is tim) [15-02-05 10:43:29:730 GMT] --------tim (My sibling is mike) [15-02-05 10:43:29:730 GMT] ------Those that need coaching (My sibling is Those that just need a little practise for the lightbulb to go off) [15-02-05 10:43:29:730 GMT] --------Those that need lots of face to face (My sibling is Those that just need some interaction) [15-02-05 10:43:29:731 GMT] ----------jim (My sibling is mary) [15-02-05 10:43:29:731 GMT] ----------mary (My sibling is jim) [15-02-05 10:43:29:732 GMT] --------Those that just need some interaction (My sibling is Those that need lots of face to face) [15-02-05 10:43:29:732 GMT] ----------fatima (My siblings are tom,barbie,ken) [15-02-05 10:43:29:732 GMT] ----------tom (My siblings are fatima,barbie,ken) [15-02-05 10:43:29:733 GMT] ----------barbie (My siblings are fatima,tom,ken) [15-02-05 10:43:29:733 GMT] ----------ken (My siblings are fatima,tom,barbie) [15-02-05 10:43:29:734 GMT] ----Those that never will (My sibling is Those that could learn) [15-02-05 10:43:29:734 GMT] ------statler (My sibling is waldorf) [15-02-05 10:43:29:734 GMT] ------waldorf (My sibling is statler)
Walkthrough
In principle this is not a lot different to the example in JavaScript recursion primer, except we are now investigating the parents of the node to be printed so we can figure out its siblings
- First, we add links to the parent of each node
var tree = addParentLinks(root);// first add parent links
- call the recursive function with the tree as an argument to kick the whole thing off
recursiveSiblings (tree);
- process the data for this node – in this case, indent & print the label, and discover the siblings and add them.
// if we didnt get a depth, start at 0
depth = depth || 0;
// indent by double the node depth
var text = indent(depth*2 , "-") + node.label;
// show any siblings
if (node.parent && node.parent.children.length > 1) {
// this will list any nodes with the same parent who is not the current node
Logger.log(text + ' (My sibling' + (node.parent.children.length > 2 ? 's are ' : ' is ') +
node.parent.children.filter(function(d) {
return d !== node;
})
.map(function(d) {
return d.label;
})
.join(",")+')');
}
else {
Logger.log(text + ' (I have no siblings) ');
}
a few things are going on here
- Only look for siblings if there is a parent (the root of the tree won’t have one), and the nodes parent has more than one child (it’s not an only child)
if (node.parent && node.parent.children.length > 1)
- A little bit of sugar to fix the grammar if there is more than one sibling (the parent has a family of more than two)
' (My sibling' + (node.parent.children.length > 2 ? 's are ' : ' is ')
- Don’t count the node being reported on as a sibling of itself
node.parent.children.filter(function(d) { return d !== node; }) - Extract the label of the sibling and bracket and join all siblings together into a list
.map(function(d) {
return d.label;
})
.join(",")+')');
- loop through each child, with the function calling itself with each child as the argument. This will cause the child to be processed (label printed), and its children processed and so on until there are no more children, then adjust the depth since we are done with this node’s children
// process the children
node.children.forEach(function(childNode) {
recursiveSiblings (childNode,depth);
});
// unindent as we're finished the children
depth--;
Walking up through the parents.
Now that we have a tree structure with parents as well as children, from any node we can walk back up through the branches to the root. We don’t even have to use recursion to do this, but since this is about recursion – and this is super simple
function showFollow() {
followUpThroughParents(addParentLinks(root).children[1].children[0].children[0].children[1]);
}
function followUpThroughParents(node) {
if(node) {
Logger.log(node.label);
followUpThroughParents(node.parent);
}
}
Gives this
[15-02-05 11:22:50:230 GMT] tim [15-02-05 11:22:50:231 GMT] Those that just need a little practise for the lightbulb to go off [15-02-05 11:22:50:231 GMT] Those that could learn [15-02-05 11:22:50:231 GMT] Those that don't [15-02-05 11:22:50:232 GMT] There are 2 kinds of people in the world
Walkthrough
- Add parent links to the source JSON object, select some random child to demonstrate with, and walk upwards to the root.
function showFollow() {
followUpThroughParents(addParentLinks(root).children[1].children[0].children[0].children[1]);
}
- if the node is defined (when we get to the root it won’t be since the root has no parent), then print the current label, and follow upwards again using the node’s parent as the argument ..etc ..etc..
function followUpThroughParents(node) {
if(node) {
Logger.log(node.label);
followUpThroughParents(node.parent);
}
}
A note about memory leaks
Most run-times have a garbage collector which runs from time to time to recover memory not being used. It defines not being used as ‘no references to it from something else’. So if you create an object in a function, then exit that function without returning the object then there will be no active references to that object, and it can be offered up for garbage collection.
With two way links like this, some garbage collectors have trouble noticing that an object is no longer referenced. This may not be the case with the JS engine used by Apps Script- it’s hard to tell, but other garbage collectors are well known for this problem (see Objects and the garbage collector for how VBA runs into this).
Just to be on the safe side, I always like to remove parent references when I’m done with an object using a tearDown function.
Another point to remember (and another good reason to use a tearDown), is that you won’t be able to JSON.stringify() an object that has two way links like this (since it would be an endless loop)
Modify the showFollow() function to remove parent links when done.
function showFollow() {
followUpThroughParents(addParentLinks(root).children[1].children[0].children[0].children[1]);
tearDown(root);
}
And the teardown function (which is also recursive) looks like this.
function tearDown(parent) {
// remove parent links
parent.children.forEach(function(d) {
// kill parent link
d.parent = null;
// then tearsdown its own childrens link
tearDown(d);
});
}
And that’s all there is to it. Happy recursing.
Why not join our forum, follow the blog or follow me on twitter to ensure you get updates when they are available.