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.
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
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 …
[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
- 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.
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
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.