Data Structure: Trees and Depth-First Tree Traversals in JavaScript

What is a tree?

Trees are a commonly-used data structure in web development. You interact with a very common example of a tree every time you use your browser, likely without knowing it — the Document Object Model (DOM).

DOM tree
Source: w3schools

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. (Source)

Trees are compromised of nodes. In talking about the relationships between these nodes, we often mix our metaphors between actual trees, and a family tree. The top-most node (or the node with no ‘parent’ node) is called the root. The bottom-most node(s) (or nodes with no child nodes), are called leaves. Nodes with both a parent node and any child nodes are called branches.

tree_conceptualVisualization

Let’s walk through an implementation of a tree in JavaScript. There are so many resources online, but here I hope to add value those existing resources by making it more accessible and clear, including visualizations.

In this implementation, each tree instance / node will have a property, ‘value’, and property ‘children’ (which will contain their child nodes, if they have any). Each will also have a method to add a child node, and to traverse  the tree in a depth-first manner.

Create a new tree

var Tree = function(value){
  var newTree = {};

  // underscore.js _.extend method
  _.extend(newTree, treeMethods);
 
  newTree.value = value;
  newTree.children = [];

  return newTree;
};

var treeMethods = {};

When we create our first new Tree instance…

var tree = Tree('A');

… we now have a tree object with a property ‘value’ (with a value of ‘A’), and a property ‘children’ (an empty array).

tree_1

Add child nodes to our tree

Let’s add a method that allows us to add children to an existing node:

treeMethods.addChild = function(value){
  this.children.push(Tree(value));
};

Note that each child node itself is also an instance of a tree. Using our new method, let’s add a few child nodes to our tree:

tree.addChild('B');
tree.addChild('C');
tree.children[0].addChild('D');
tree.children[1].addChild('E');
tree.children[1].addChild('F');

Our tree now looks like this:

tree_2

Traverse the tree, depth-first

Traversing our tree depth-first means that we’ll first visit our ‘deepest’ or ‘lowest’ nodes, and ultimately visit our root node.

tree_3

treeMethods.traverseDF = function(callback) {
  function recurse(currentNode) {
    for (var i = 0; i < currentNode.children.length; i++) {
      recurse(currentNode.children[i]);
    }
    callback(currentNode);
  }
  recurse(this);
}

Reference: code.tutsplus.com

As an example, we’ll call our traverseDF method with an anonymous callback:

tree.traverseDF(function(node) {
    console.log(node.value)
});

*Note: If you are comfortable with recursion, skip this. If, like me, your understanding of recursion does not come naturally, feel free to come on this journey with me.

Our ‘recurse’ function inside traverseDF kicks off our recursion on ‘this’, which in our above call points to ‘tree’. So our first considered ‘currentNode’ is our root node, the tree instance with the value of ‘A’. We call ‘recurse’ on our ‘A’ node.

That call to recurse creates a new loop (1) over the child nodes of the ‘A’ node — ‘B’ and ‘C’.

tree_14
Note: We wouldn’t actually call “recurse(‘A’)”. It’s just representative of what’s happening.

The first iteration of loop (1) calls ‘recurse’ on node ‘B’ (tree.children[0]).

That call to ‘recurse’ creates a new loop (2) over the child nodes of the ‘B’ node. Here, that’s only one — ‘D’.

tree_15

The call to ‘recurse’ on node ‘D’ does not create a loop (‘D’ has no child nodes), and so that code is skipped, and we run our callback on the currentNode, ‘D’.

tree_16a

Since ‘D’ is the only node in loop (2), that loop is finished. We exit the loop from the ‘recurse’ call to node ‘B’ (or, the first child node of ‘A’), and call our callback on the currentNode, ‘B’.

tree_17

We continue on in our loop (1) over the child nodes of ‘A’, calling ‘recurse’ on our node ‘C’.

tree_18

That call to ‘recurse’ creates a new loop (3) over the child nodes of the ‘C’ node. Here, that’s two — nodes ‘E’ and ‘F’.

tree_19

The first iteration of loop (3) calls ‘recurse’ on node ‘E’. That call does not create a loop (‘E’ has no child nodes), and so that code is skipped, and we run our callback on the currentNode, ‘E’.

tree_20

The second iteration of loop (3) calls ‘recurse’ on node ‘F’. That call does not create a loop (‘F’ has no child nodes), and so that code is skipped, and we run our callback on the currentNode, ‘F’.

tree_20a

Since ‘F’ is the last node in loop (3), that loop is finished. We exit the loop from the ‘recurse’ call to node ‘C’ (or, the second child node of ‘A’), and call our callback on the currentNode, ‘C’.

tree_21

Since ‘C’ is the last node in loop (1), that loop is finished. We exit the loop from the original ‘recurse’ call to node ‘A’, and call our callback on the currentNode, ‘A’.

tree_22

At the end of the day, our call to the traverseDF method…

tree.traverseDF(function(node) {
    console.log(node.value)
});

… ends up returning …

D
B
E
F
C
A

References

 

Leave a Reply

Your email address will not be published. Required fields are marked *