Data Structures — Traversing Trees

AKA Swinging Through Trees

This post is the third part of a multi-part series on Data Structures. To check out the previous post on Linked Lists and Doubly Linked Lists, click here.

If you’re like me, traversing Data Structures can be one the most elusive concepts of JavaScript. They can make sense and not make sense all at the same time. Sure it can be intuitive — you start with your parent node, then that parent has a child node, and that child node has more child nodes, and so on and so forth, but every time I try to traverse one my reality comes crashing down and I feel like I don’t understand how to take that next step. Sure we can litter our program with a bunch of for loops, but that’s just time-consuming and inefficient. So what’s the point of using data structures if we have objects and arrays? Put simply, data structures allow us to structure and manipulate data in ways that arrays and objects cannot. In order to truly master traversing data structures, it is important to at least have an understanding of how recursion works so that we can save ourselves from having to rewrite the same code over and over and over. Although there are numerous types of data structures out there, this post will be focusing on how to create, modify, and traverse a Tree Data Structure.

Trees — What, why and how?
Tree Data Structures allows us to structure data hierarchically, making information easy to search through while allowing us to easily manipulate data. Tree Data Structures are made of a root value and child nodes (AKA subtrees with a parent node) represented as a set of linked nodes. Let’s unpack that for a second. We know that a Tree Data Structure will have a root value. We know that it will also contain child nodes that mirror the parent structure. Finally, we know that the parent and child node will be represented as a set of linked nodes. Let’s see if we can write this out:

var Tree = function(value) {
  this.value = value; //here is where we are setting our root value 
  this.children = []; //here the children array will store the 
    // values of our child node.
}
Tree.prototype.addChild = function(value) {
  var child = new Tree(value); //setting the value of the child node
  return this.children.push(child); //pushing the new child node 
    // onto the Tree
}
var treeDataStructure = new Tree(1); //creates a new Data Structure 
  // based on the original Tree class
console.log(treeDataStructure); // { value: 1, children: [] }
treeDataStructure.addChild(2); //adds a child value onto the newly 
  // created data structure
console.log(treeDataStructure) // { value: 1, children: [ { value: 
  // 2, children: [] } ] }

Here we’ve created a Class function that can create our tree structure, but it may not be clear just how this information is stored. Furthermore, how can we know that what we’re creating is actually a tree? Before trying to create and traverse any Data Structure, it always helps drawing it out in order to get a better understanding of how your output should look. This will help prevent careless mistakes while allowing you to visually represent the nature of your program.

Here we have an example of how a Tree Data Structure should look like

As the above diagram shows, our Tree structure has a root value (2) at the top, with child node values of 7 and 5. These child nodes are then parents to more children until they reach their final destination. If taken individually, it is easier to see that a child node is simply a nested parent node. This distinction may help create a pattern of understanding when we start traversing the Tree.

Tree Traversal — Be Like Tarzan:
Now that we’ve got an idea and mental image of how Tree Data Structures work, we can start trying to implement our knowledge by traversing through it. Although it may not seem like much fun, this is where we can get truly creative with our ideas. Let’s start off by drawing what our Tree Structure is supposed to look like.

Now that we’ve got a visual representation of what our structure looks like, it should be easier to imagine what we’d like our program to do. Let’s say we wanted to apply a filter function onto each value in our Tree object, we can imagine that we would have to search every node in the tree and filter their values, ultimately returning the filtered tree values. Since we know that our output will be different than our input, we should create an array to hold our ever-changing results. Since we want this method to be applicable for every node of the tree, we can create a subroutine to recursively run the function at deeper and deeper levels.

//This method is an extension of the previous Tree Class
Tree.prototype.filterFunction = function(filter) {
  var result = []; //We are using this array to store the results
  
  //creating a subroutine can help compartmentalize recursion
  var filtered = function(obj) { 
    if (filter(obj.value)) {
      result.push(obj.value);
    }
    for (var i = 0; i < obj.children.length; i++) {
      filtered(obj.children[i])
    }
  };
  filtered(this); //sets the initial this value and runs the 
    //recursive call
  return result;
};

Here we’ve added a method onto our Tree Class that will take a filter function as an argument and return the filtered values of that Tree. By implementing a subroutine, we can easily implement a recursive function that will explore every child node and sibling without having to create a high number of checks. As was mentioned earlier, child nodes have the same structure and properties as the parent. By using a for loop, we can confidently access each child node without having to worry about our recursive call exceeding the maximum call stack. We can therefore guarantee that our method will apply the filter function onto each of the values within the Tree Data Structure.

I hope this was able to help animate how Tree Data Structures are formed! For more information on Trees and the terminology used in them, check out this wikipedia page.

Recap
- Tree structures are comprised of nodes that have a value and child property.
- Information within a Tree can be traversed breath or depth first.
- Each child node has a value and a child property.

This is Part III of a multi-part series on Data Structures. If you’re interested in continuing on with the series on Data Structures, check out this next post to see how to create a graph.