Data structures with JavaScript: Wood

End product imageEnd product imageEnd product image
What you want to create

* {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 widely used data structures in web development. This statement applies to 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, in turn, has consumed information on the Internet has received it in the form of a tree – DOM.

That’s right, the article you’re currently reading is rendered in your browser like a tree! The paragraph you are reading is represented as text in a <p> element; that <p> element is embedded inside a <body> element; and <body> element is embedded inside a <html> element.

JUDGMENT OF A SITEJUDGMENT OF A SITEJUDGMENT OF A SITE
Document object model of an HTML page

Embedding data looks like a family tree. That <html> element is a parent, the <body> element is a child, and <p> element is a child of <body> element. If this analogy of a tree seems useful to you, then you will find solace 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 tree crawling methods: depth-first-search (DFS) and width-first-search (BFS). (If the word traversal is unfamiliar to you, consider it to mean visiting every node on the tree.) Both of these types of traversal highlight different ways of interacting with a tree; both journeys also incorporate the use of data structures that we have covered in this series. DFS uses a stack, and BFS uses a queue to visit nodes. It is cool!

Crossing a tree with depth-first-search and width-first-search

In computer science, a tree is a data structure that simulates hierarchical data with nodes. Each node in a tree has its own data and points to other nodes.

The terminology for notes and pointers may be new to some readers, so let’s describe them further with an analogy. Let’s compare a tree with an organization chart. The chart has a position at the top level (root node), such as the CEO. Directly below this position are other positions, such as Vice President (VP).

Organizational treeOrganizational treeOrganizational tree
Organizational tree

To represent this relationship, we use arrows pointing 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 benchmark. To create more relationships in our organization chart, we just repeat this process – we have one node to another node.

On a conceptual level, I hope that notes and pointers make sense. At the practical level, we can advantageously use a more technical example. Let us consider the JUDGMENT. A JUDGMENT has one <html> element as its top-level position (root node). This node points to one <head> element and a <body> element. This structure is repeated for all nodes in DOM.

One of the beauties of this design is the ability to embed nodes: a <ul> element can have many, for example <li> elements embedded inside it; in addition, each <li> element may have siblings <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 element without children – a leaf – is found. And then it goes back from the leaf node and visits the latest node that has not yet been explored.

DFSDFSDFS
Depth-first search

Breadth-First Search (BFS)

In a width-first search, the tree passage starts from the root node and first crosses all the neighboring nodes. It then selects the nearest node and explores the new nodes. This method is repeated for each node until it reaches the destination.

BFSBFSBFS
Width-first search

Operations of a tree

Since each tree contains nodes that can be a separate constructor from a tree, we will outline the operations for both constructors: Node and Tree.

Note

  • data saves a value
  • parent points to the parent of a node
  • children points to the next node in the list

Tree

  • _root points to the root node of a tree
  • find(data): returns the node that contains the given data
  • add(data, parentData): add a new node to the parent that contains the given data
  • remove(data): remove the node containing the given data
  • forEach(callback): Run a recall on each node in the tree in depth-first order
  • forEachBreathFirst(callback): Run a recall on each node in the tree in width-first order

Implementing a tree in JavaScript

Now let’s write the code for a tree!

That Node grade

For our implementation, we will first define a class by name Node and so called a constructor Tree.

Each instance of Node contains three properties: data, parentand children. The first property contains data associated with a payload of the node tree. parent points to the individual node that this node is the child of. children points to all child nodes in this node.

That Tree grade

Let us now define our constructor for Treewhich covers Node designer in its definition:

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

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

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

Methods for Tree

Next, we will create the following five methods:

  • find(data): returns the node that contains the given data
  • add(data, parentData): add a new node to the parent that contains the given data
  • remove(data): remove the node containing the given data
  • forEach(callback): Run a recall on each node in the tree in depth-first order
  • forEachBreathFirst(callback): Run a recall on each node in the tree in width-first order

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

Depth-first search with find(data)

This method crosses a tree with depth-first search.

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 as the tree root and is later used to go back over the child nodes.

That for iterates over each child of node, beginning with the first child. Inside the body of for loop, we invoke find() work recursively with the child. Once the data is found, it will be returned throughout the stack of function calls, ending the search.

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

Note that this is a depth-first search – find will recursively drill down to the tree’s leaf nodes and work its way up again.

Understanding recursion

Recursion is a very difficult subject to teach and requires an entire article to explain it adequately. Since the explanation of recursion is not the focus of this article – the focus is the implementation of a tree – I would suggest that all readers who lack a good understanding of recursion experiment with our implementation of find() and try to understand how it works.

I want to include a live example below so you can try it.

Adding elements to the tree

Here is the implementation of our add method:

That 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 is found, we add the new node to the parents’ list of children. We will also attach the parent to the new node. Now the new node is attached to its place in the tree.

Removal of items from the tree

How to implement our removal method:

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

Depth-first wood walk with forEach()

Next, we add one forEach() method to our tree so we can cross it and apply a custom recall to each node.

Just like find() method, this is an in-depth first review. This will visit each node in the tree, beginning at the base of the first branch and working its way through the entire tree. Imagine an ant crawling from one leaf, up the branch and then down again to another leaf, and so on.

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

in forEach() calls, we created a simple callback that logs each node to the console when visited. If we run this code, we get the following output.

Bredth-First Traversal Med forEachBreadthFirst()

For most applications, a depth-first search is simpler and just as effective, but sometimes a width-first review is required. Here is our last method Tree grade.

Where a depth-first crawl uses recursion to search the tree, the width-first crawl uses a queue structure. As each node is visited, its children are pushed to the back of the queue. The next nodes to be visited are taken from the front of the queue, ensuring that higher-level nodes are visited before their child nodes.

Uses the same tree as above if we cross the tree with forEachBreadthFirst(), we visit the notes in a different order. Here is the code:

And here is the review it produces:

As you can see, the notes are crossed this time from top to 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 crossing them.

Conclusion

Trees simulate hierarchical data. Much of the world around us is similar to this type of hierarchy, such as web pages and our families. Whenever you need to structure data with hierarchy, consider using a tree!

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

Leave a Comment