More recursion – parents and children

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.

Now we need to add a parent to each node, so it will look like this.

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….
and we call it like this, passing the root of the tree we created in JavaScript recursion primer.

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.
Here’s the updated version.

and the result …

Note that each node now also shows its sibling(s) in brackets

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
  • call the recursive function with the tree as an argument to kick the whole thing off
  • process the data for this node – in this case, indent & print the label, and discover the siblings and add them.
a few things are going on here

  1. 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)
  2. 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)
  3. Don’t count the node being reported on as a sibling of itself
  4. Extract the label of the sibling and bracket and join all siblings together into a list
  • 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

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
Gives this

Walkthrough

  • Add parent links to the source JSON object, select some random child to demonstrate with, and walk upwards to the root.
  • 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..

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.
And the teardown function (which is also recursive) looks like this.
And that’s all there is to it. Happy recursing.

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.