Using arrow functions for recursive post-order tree traversal

Created:24 Jul 2020 00:31:31 , in  Maths

JavaScript arrow functions are cool addition to the language. You no longer think about a good name for your function, are allowed to skip "function" keyword, and sometimes even drop parameter's enclosing parentheses. In this article I look at whether these function with slimmed down syntax are any good for recursion and traversing tree data structure. One, very useful way of traversing trees is based on post-order technique, which, apart from aforementioned functions is the other major theme of this article.

Bottom-top approach to traversing trees

Post-order tree traversal technique can be described in many ways. One simple analogy is this: suppose you have a great idea in mind. However, it is a complex and multi-level one, you know that for the idea to actually come to fruition you will need to build good foundations and more. So, you will need to get to the of what's needed and either find project-ready or build components for your idea by yourself. Then, you put these components together to get a level higher, or more accurately, a level closer to your goal. As you climb up, your components contain more and more low-level components and you get closer and closer to the working version of your idea, and eventually reach the point when the whole thing is ready for a launch.

Post-order traversal is a lot like the process above, you have a reference to the top node of your tree (so, you know where you start and where you want to end), but have to come down and visit the bottom-most nodes first, their parents and so on, before eventually reaching the root node again.

Post-order tree traversal with JS arrow functions

Let's look how to get an arrow function to work recursively now. One important thing about JavaScript arrow functions in, most of the time, they are not named. They receive parameters, they have a body, but not a name. To call such a function recursively, which implies more than once, you need to give it a name first. Below is a factorial function based on post-order tree traversal technique, which shows how to deal with this problem.

var factorial = n => {
  if( n === 0 ){
    return 1;
  }
  return n * factorial(n - 1);   
}

factorial(5)
// => 120  

Once an arrow function has a name, factorial in the case above, it is very much a business as usual. Little difference or advantage over the old ways here.

Tree traversal and collection of values based on post-order

The next piece of code is more involved. It helps not just traverse but also collect all the values from all the nodes in a tree. Bottom nodes are going to be visited first.

Here is a short description of what happens here: firstly a few disconnected nodes are created and values assigned to them, then the nodes get connected and end up as a tree. Once the tree is ready, a recursive tree traversal and value collection function described. The function receives a root node of a tree, and starts collecting vales at the bottom-most node of the tree. Eventually, All values are collected in an array and returned.

// a blueprint function for tree nodes
function Node(){
  this.value = null;
  this.children = []; 
}

// create some nodes
var a = new Node;
var b = new Node;
var c = new Node;
var d = new Node;
var e = new Node

// assign values to each node
a.value = "a";
b.value = "b";
c.value = "c";
d.value = "d";
e.value = "e";

// turn nodes into a tree
a.children.push(b);
a.children.push(c); 
a.children.push(d);
d.children.push(e);

// tree traversal and value collection function
var postOrderTreeTraversal = (tree,values = []) => {
  if(tree.children.length === 0){
    values.push(tree.value)
    return values;
  }  
  
  tree.children.forEach( child => {
    values = postOrderTreeTraversal( child,values );
  })
  values.push(tree.value);
  return values;
}

// call the function 
postOrderTreeTraversal(a);
//=> ['b','c','e','d','a'];

One thing worth noting about postOrderTreeTraversal function is, its second parameter is an empty array. It is a default parameter. Default parameters for functions are available in ES6, but not in ES5.

Conclusion

As you can see, recursive post-order tree traversal can be done using JavaScript arrow functions in pretty much the same way it had been done with named functions before the new syntax arrived. One thing, to remember is, an arrow function has to be named before it can be called repeatedly. Once done, things look and behave very much the old way.

I hope you have enjoyed the article and have found it useful. If you have something to add, leave a comment below.

This post was updated on 24 Jul 2020 01:28:44

Tags:  data structure ,  JavaScript ,  recursion