Binary tree in JavaScript

Binary trees are a tree data structure that are used in computer science. A binary tree consists of a root, which is the top node in the tree and each node has a pointer towards its children (if any). Each node in the tree can have maximum of two children, also rererred as left and right children. Binary trees are most common to be used in searching and sorting data due to its hierarchical structure.

Each node in the tree has 3 properties.

• value
• left child reference pointer
• right child reference pointer

An example of a binary tree is shown in the image below.

In this article, we will be implementing a binary tree in JavaScript. Our program will be able to insert nodes, delete a node (and its references) and print the whole tree as well as the indivdual nodes.

Create the Node class

We will begin with creating our Node class. As we already know, we need to give it its three properties - left, right and the value. When creating a new node, we want to give it its value in the constructor.

class Node {
  left;
  right;
  value;

  constructor(value) {
    this.value = value;
  }
}

Create the Tree class

We will continue on with our Tree class. Our Tree will only have one property, which is the root of the tree. When creating the Tree, we want to initialize our root node as well.

class Tree {
  root;

  constructor(rootValue) {
    this.root = new Node(rootValue);
  }
}

Now the first part of our Tree is done. We are now able to create a binary tree, with the root node.

const tree = new Tree(1);

However, we now want to be able to add nodes to the tree, so that we can make a real binary tree.

Insert nodes

In order to add our new node to the tree, we need to find the correct node to add the new node as a child to. We will follow this logic:

• Search recursively for the first node in the tree that has < 2 children
• When the node is found, add the new child as a left reference if left is null, otherwise add to the right

Let's start with creating our public function that our Tree class will expose:

  insertNode(value) {
    const nextNode = this._findEmptyNode(this.root);
    if (!nextNode.left) {
      nextNode.left = new Node(value);
    } else {
      nextNode.right = new Node(value);
    }
  }

In this function, we are calling the private _findEmptyNode() function (which we will implement next), and when the node is found, we will check if it should add the new node to the left or right pointer.

Now we will implement our _findEmptyNode() function, which will search through the tree for the next empty node. We will also create a small util function, called _isFull to check if a node has two children already, just to keep the code more readable. In our Tree class, we add these two functions as below:

  _isFull(node) {
    return node?.left && node?.right;
  }

  _findEmptyNode(node) {
    // We found the next node
    if (!node.left || !node.right) {
      return node;
    }

    // If the node has children that are full, we will search to the left. Else, if only the left side is full, we will search to the right
    if (this._isFull(node.left) && this._isFull(node.right)) {
      return this._findEmptyNode(node.left);
    } else if (this._isFull(node.left)) {
      return this._findEmptyNode(node.right);
    }
    // If neither left or right is full, we will search to the left
    return this._findEmptyNode(node.left);
  }

And now, we are ready to insert nodes to the tree, as follows:

const tree = new Tree(1);
tree.insertNode(2);
tree.insertNode(3);

Delete a node

Next up on our journey, is to implement to ability to remove a node (and all its references) from the tree. The logic is as follows:

• Search for the node using the value as reference
• When/if node is found, we recursively remove the children of the node

Let's start with our public function that our Tree class will expose, we will call it deleteNode

  deleteNode(value) {
    const node = this._findNode(this.root, value);
    this._deleteNodeAndLeafs(node);
  }

Here, we are finding the node with our private _findNode() function that we will implement next, and then we are passing in the node to another private function called _deleteNodeAndLeafs that will recursively remove the children down the tree structure.

_findNode(node, value) {
    // Return null of the node is undefined
    if (!node) {
      return null;
    }

    // When node is found, we return it
    if (node.value === value) {
      return node;
    }

    // Search both left and right side of the tree (|| works since we are returning null if the search hit the bottom of the tree if(!node))
    return (
      this._findNode(node.left, value) || this._findNode(node.right, value)
    );
  }

The above function, will search until it finds the node with the value that we are searching for. And once found, we will return it.

Next, we will create our _deleteNodeAndLeafs function as follows

  _deleteNodeAndLeafs(node) {
    if (!node) {
      return null;
    }
    // Store the node in constants
    const nextLeft = node.left;
    const nextRight = node.right;

    // Remove the pointers and value
    delete node.left;
    delete node.right;
    delete node.value;

    return (
      this._deleteNodeAndLeafs(nextLeft) || this._deleteNodeAndLeafs(nextRight)
    );
  }

Above function, will go through each node that is below our node that we want to remove and delete each and one of them. We will do it in a similar fashion as the previous function for removing both left and right children (and their children etc - until we hit the bottom of the hierarchy).

Then, we can use our function as below:

const tree = new Tree(1);

tree.insertNode(2);
tree.insertNode(3);
tree.insertNode(4);

tree.deleteNode(4);

Print tree and nodes

To print the tree, we can use the known tree traversal algorithm to print the nodes and their children. However, it is not always that easy to follow, especially if you are new to binary trees - so we will create a function as well that will print all nodes in the tree as well to easier visualize it.

Tree traversal

We will create the tree traversal print in our Tree class as well, and it goes as follows:

  printTree(node) {
    if (!node) {
      return;
    }
    this.printTree(node.left);
    console.log(node.value);
    this.printTree(node.right);
  }

And we call it as below:

const tree = new Tree(1);
tree.insertNode(2);
tree.insertNode(3);

tree.printTree(tree.root);

The output will then be:

2
1
3

For bigger trees, this will look confusing. So let's create a new printing function, for printing all our nodes.

Print individual nodes

In our Tree class, we add following function as well

  printNodes(node) {
    if (!node || (!node.left && !node.right)) {
      return;
    }
    console.log("\x20\x20\x20" + node.value);
    console.log("\x20" + node.left?.value + "\x20\x20\x20" + node.right?.value);
    console.log("********");
    this.printNodes(node.left);
    this.printNodes(node.right);
  }

This will basically go through each node and print the value of the node, and the value of its children. The output will look something like this after we call it:

const tree = new Tree(1);
tree.insertNode(2);
tree.insertNode(3);

tree.printNodes(tree.root);

   1
 2   3
********

And if we add some new nodes:

tree.insertNode(4);
tree.insertNode(5);

The output will look like this:

   1
 2   3
********
   2
 4   5
********

Our node with the value 2 has gotten two new children. And just to demonstrate, we can add two more that should be referenced under the node with value 3

tree.insertNode(6);
tree.insertNode(7);

Output:

   1
 2   3
********
   2
 4   5
********
   3
 6   7
********

And there we go. Now it is easier to follow the nodes in the tree and to see where the children are being placed. Next challenge would be to print the whole tree in a sleek output - but that is a task I'll leave to you 😉.

Summary

In this article, we discussed binary trees. What it is and how we can implement our own tree in JavaScript with some nice capabilities. Binary trees are a fundamental data structure that I think most of us that have a degree in Computer science have studied, one way or another.

I hope you enjoyed this guide, and as always - if you have any feedback, questions or improvements, please contact us.

Have a great day!