Data Structures With JavaScript: Tree

Final product image — What You’ll Be Creating

* { box-sizing: border-box; } body {margin: 0;}*{box-sizing:border-box;}body{margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0px;}

Trees are one of the most commonly used data structures in web development. This statement holds true for both developers and users. Every web developer who has written HTML and loaded it into a web browser has created a tree, which is referred to as the Document Object Model (DOM). Every user of the Internet who has, in turn, consumed information on the Internet has received it in the form of a tree—the DOM.

That’s right, the article that you are reading at this moment is rendered in your browser as a tree! The paragraph that you are reading is represented as text in a <p> element; the <p> element is nested inside a <body> element; and the <body> element is nested inside an <html> element.

DOM of a Website — Document Object Model of an HTML Page

The nesting of data is similar to a family tree. The <html> element is a parent, the <body> element is a child, and the <p> element is a child of the <body> element. If this analogy of a tree seems useful to you, then you will find comfort in knowing that more analogies will be used during our implementation of a tree.

In this article, we will create a tree using two different methods of tree traversal: depth-first search (DFS) and breadth-first search (BFS). (If the word traversal is unfamiliar to you, consider it to mean visiting every node of the tree.) Both of these types of traversals highlight different ways of interacting with a tree; both travels, moreover, incorporate the use of data structures that we’ve covered in this series. DFS uses a stack and BFS uses a queue to visit nodes. That’s cool!

Traversing a Tree With Depth-First Search and Breadth-First Search

In computer science, a tree is a data structure that simulates hierarchical data with nodes. Each node of a tree holds its own data and pointers to other nodes.

The terminology of nodes and pointers may be new to some readers, so let’s describe them further with an analogy. Let’s compare a tree to an organizational chart. The chart has a top-level position (root node), such as CEO. Directly underneath this position are other positions, such as vice president (VP).

To represent this relationship, we use arrows that point from the CEO to a VP. A position, such as the CEO, is a node; the relationship we create from a CEO to a VP is a pointer. To create more relationships in our organizational chart, we just repeat this process—we have a node point to another node.

On a conceptual level, I hope that nodes and pointers make sense. On a practical level, we can benefit from using a more technical example. Let’s consider the DOM. A DOM has an <html> element as its top-level position (root node). This node points to a <head> element and a <body> element. This structure is repeated for all nodes in the DOM.

One of the beauties of this design is the ability to nest nodes: a <ul> element, for instance, can have many <li> elements nested inside it; moreover, each <li> element can have sibling <li> nodes.

Depth-First Search (DFS)

The depth-first search or DFS starts at the initial node and goes deeper into the tree until the desired element or an element with no children—a leaf—is found. And then, it backtracks from the leaf node and visits the most recent node that is not yet explored.

Breadth-First Search (BFS)

In a breadth-first search, the tree traversal starts from the root node and first traverses all the neighboring nodes. Then, it selects the nearest node and explores the new nodes. This method is repeated for each node until it reaches the destination.

Operations of a Tree

Since every tree contains nodes, which can be a separate constructor from a tree, we will outline the operations of both constructors: Node and Tree.

Node

data stores a value
parent points to a node’s parent
children points to the next node in the list

Tree

_root points to the root node of a tree
find(data): return the node containing the given data
add(data, parentData): add a new node to the parent containing the given data
remove(data): remove the node containing the given data
forEach(callback): run a callback on each node of the tree in depth-first order
forEachBreathFirst(callback): run a callback on each node of the tree in breadth-first order

Implementing a Tree in JavaScript

Now let’s write the code for a tree!

The `Node` Class

For our implementation, we will first define a class named Node and then a constructor named Tree.

class Node {
    constructor(data) {
      this.data = data;
      this.parent = null;
      this.children = [];
    }
  }

Every instance of Node contains three properties: data, parent, and children. The first property holds data associated with a node—the payload of the tree. parent points to the single node that this node is the child of. children points to all the child nodes of this node.

The `Tree` Class

Now, let’s define our constructor for Tree, which includes the Node constructor in its definition:

class Tree {
    constructor(data) {
      let node = new Node(data);
      this._root = node;
    }
    
    //other Tree methods...
  }

Tree contains two lines of code. The first line creates a new instance of Node; the second line assigns node as the root of a tree.

The definitions of Tree and Node require only a few lines of code. These lines, however, are enough to help us simulate hierarchical data. To prove this point, let’s use some example data to create an instance of Tree (and, indirectly, Node).

let tree = new Tree('CEO');

  // {data: 'CEO', parent: null, children: []}
  tree._root;

Thanks to the existence of parent and children, we can add nodes as children of _root and also assign _root as the parents of those nodes. In other words, we can simulate the creation of hierarchical data.

Methods of `Tree`

Next, we will create the following five methods:

find(data): return the node containing the given data
add(data, parentData): add a new node to the parent containing the given data
remove(data): remove the node containing the given data
forEach(callback): run a callback on each node of the tree in depth-first order
forEachBreathFirst(callback): run a callback on each node of the tree in breadth-first order

Since the add and remove methods require us to find a specific node, we’ll start with that method, using a depth-first search.

Depth-First Search With `find(data)`

This method traverses a tree with depth-first search.

    //returns the node that has the given data, or null
    //use a depth-first search 
    find(data, node = this._root) {
        //if the current node matches the data, return it
        if (node.data == data)
            return node;

        //recurse on each child node
        for (let child of node.children) {
            //if the data is found in any child node it will be returned here 
            if (this.find(data, child))
                return child;
        }   
        
        //otherwise, the data was not found
        return null;
    }

find() is a recursive function with a parameter for the data to find and for the node to search under. find also has a parameter for the current node—this starts out as the tree root, and is later used to recurse over the child nodes.

The for iterates over each child of node, beginning with the first child. Inside the body of the for loop, we invoke the find() function recursively with that child. When the data is found, it will be returned back through the whole stack of function calls, terminating the search.

If no matching node is found, null will be eventually returned.

Note that this is a depth-first search—find will recursively drill down to the leaf nodes of the tree and work its way back up.

Understanding Recursion

Recursion is a very hard topic to teach and requires an entire article to adequately explain it. Since the explanation of recursion isn’t the focus of this article—the focus is implementing a tree—I’ll suggest that any readers lacking a good grasp of recursion experiment with our implementation of find() and try to understand how it works.

I’ll include a live example below so you can try it out.

Adding Elements to the Tree

Here’s the implementation of our add method:

    //create a new node with the given data and add it to the specified parent node
    add(data, parentData) {
        let node = new Node(data);
        let parent = this.find(parentData);

        //if the parent exists, add this node
        if (parent) {
            parent.children.push(node);
            node.parent = parent;

            //return this node
            return node;
        }
        //otherwise throw an error
        else {
            throw new Error(`Cannot add node: parent with data ${parentData} not found.`);
        }
    }

The add method lets us specify the data for the new node, and also the parent node we want to add it to.

First we search for the parent node with the given data. If it’s found, we’ll add the new node to the parent’s list of children. We’ll also link the parent to the new node. Now the new node is linked into its place in the tree.

Removing Elements From the Tree

Here’s how we’ll implement our remove method:

    //removes the node with the specified data from the tree
    remove(data) {
        //find the node
        let node = this.find(data)

        //if the node exists, remove it from its parent
        if (node) {
            //find the index of this node in its parent
            let parent = node.parent;
            let indexOfNode = parent.children.indexOf(node);
            //and delete it from the parent
            parent.children.splice(indexOfNode, 1);
        }
        //otherwise throw an error
        else {
            throw new Error(`Cannot remove node: node with data ${data} not found.`);
        }
    }

Just like for the add method, first we search for the node with the given data. When we find it, we can delete that node and all of its children from the tree by removing it from its parent. Here we use indexOf() to find the node in the parent’s list of children, then we use splice() to delete it from that list.

Depth-First Tree Traversal With `forEach()`

Next we’ll add a forEach() method to our tree so that we can traverse it and apply a custom callback to each node.

    //depth-first tree traversal
    //starts at the root
    forEach(callback, node = this._root) {
        //recurse on each child node
        for (let child of node.children) {
            //if the data is found in any child node it will be returned here 
            this.forEach(callback, child);
        }   
        
        //otherwise, the data was not found
        callback(node);
    }

Just like the find() method, this is a depth-first traversal. This will visit each node in the tree, starting at the bottom of the first branch and working its way through the whole tree. Imagine an ant crawling from one leaf, up the branch and then back down to another leaf, and so on.

We can test the traversal out with by creating a new tree as below.

let t = new Tree("CEO");
t.add("VP Finance", "CEO");
t.add("VP Sales", "CEO");
t.add("Salesperson", "VP Sales");
t.add("Accountant", "VP Finance");
t.add("Bookkeeper", "VP Finance");

t.forEach(node => console.log(node.data));

in the forEach() call, we created a simple callback that logs each node to the console as it is visited. If we run this code, we’ll get the following output.

Accountant
Bookkeeper
VP Finance
Salesperson
VP Sales
CEO

Breadth-First Traversal With `forEachBreadthFirst()`

For most uses, a depth-first search is simpler and just as effective, but sometimes a breadth-first traversal is called for. Here’s our final method of the Tree class.

    //breadth-first tree traversal
    forEachBreadthFirst(callback) {
        //start with the root node
        let queue = [];
        queue.push(this._root);
    
        //while the queue is not empty
        while (queue.length > 0) {
            //take the next node from the queue  
            let node = queue.shift();
            
            //visit it
            callback(node);

            //and enqueue its children
            for (let child of node.children) {
                queue.push(child);
            }
        }
    }

Where a depth-first traversal uses recursion to search the tree, the breadth-first traversal uses a queue structure. As each node is visited, its children are pushed on to the back of the queue. The next nodes to visit are taken from the front of the queue, which ensures that higher-level nodes are visited before their child nodes.

Using the same tree as above, if we traverse the tree with forEachBreadthFirst(), we’ll visit the nodes in a different order. Here’s the code:

t.forEachBreadthFirst(node => console.log(node.data));

And here’s the traversal it produces:

CEO
VP Finance
VP Sales
Accountant
Bookkeeper
Salesperson

As you can see, this time the nodes are traversed from the top to the bottom.

Interactive Example of a JavaScript Tree Structure

Here is an interactive example with all the code from this post. You can experiment with creating different trees and modifying or traversing them.

Conclusion

Trees simulate hierarchical data. Much of the world around us resembles this type of hierarchy, such as web pages and our families. Any time you find yourself in need of structuring data with hierarchy, consider using a tree!

A freelance web developer and a technical writer, Subha Chanda has a passion for learning and sharing experiences with others.