Tag: Trees

I recently started reading Data Structures and Algorithms With JavaScript by Michael McMillan. Not having an academic background in computer science I’ve tended to shy away from this subject. With front-end development becoming an ever more complex endeavor, however, I felt it was about time to dive in and see what I’ve been missing. This and somebody recently asked me a question about binary search trees, about which I was utterly clueless. Guilt can be a good motivator, I guess.

What are trees?

McMillan defines a tree as a “nonlinear data structure that is used to store data in a hierarchical manner.” In this context a nonlinear data structure can be defined as a data structure in which data is arranged randomly, while a hierarchical data structure can be defined as a data structure in which data is organized into levels. A specific terminology is used when discussing trees. Some terms I’ll be using in this post include:

• Root
• Child
• Parent
• Leaf
• Edge
• Path
• Level
• Depth
• Key value

Binary trees and binary search trees are special kinds of tree. In a binary tree, a node can have no more than two child nodes; in a binary search tree (BST), lesser values are stored in left nodes and greater values are stored in right nodes. The following diagram depicts a binary search tree.

In this post I’ll be creating this BST using ES6 and adding some methods to it for adding and retrieving data. The code for my creation is available on CodePen.

Creating the BST

Creating the empty BST turns out to be relatively straightforward. All that’s needed is a class to represent a node and a class to represent the BST. A node holds references to the data it’s supposed to store as well as to its children (left and right nodes). The BST holds a reference to the root, which starts out as null. The basic classes end up looking like this:

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
}

Notice how the values of a node’s children are initialized using ES6 default parameters. Creating the BST is a simple matter of instantiating the BST class: const bst = new BST();.

Adding nodes to the BST

So far so good but an empty tree isn’t much use to anyone. In order to add nodes to the tree we’re going to need a method for doing so. Following is the insert() method McMillan defines, translated to ES6 from his ES5:

class BST {
  ...
  insert(data) {
    const node = new Node(data);
    if (this.root === null) {
      this.root = node;
    } else {
      let current = this.root;
      let parent;
      while(true) {
        parent = current;
        if (data < current.data) {
          current = current.left;
          if (current === null) {
            parent.left = node;
            break;
          }
        } else {
          current = current.right;
          if (current === null) {
            parent.right = node;
            break;
          }
        }
      }
    }
  }
}

The insert() method works by creating a new node and passing any data it was passed into the new node’s constructor. The method then does one of two things:

1. If the BST doesn’t have a root, it makes the new node the root.
2. If the BST does have a root, it traces a path through the BST until it finds an insertion point for the new node. Essentially this involves determining whether the new node should be inserted as the left or right child of a given parent. This is based on whether the new node’s value is lesser or greater than the parent’s value.

So let’s go ahead and insert some nodes and see how this works in practice.

bst.insert(4);
bst.insert(2);
bst.insert(6);
bst.insert(1);
bst.insert(3);
bst.insert(5);
bst.insert(7);

Following is a table that illustrates the inner workings of the insert() method for each of the values we’re inserting. (A key to the column headings follows the table.)

1	2	3	4	5	6	7
4	null	n/a	n/a	n/a	n/a	insert
2	4	4	true	left	null	insert
6	4	4	false	right	null	insert
1	4	4	true	left	2	iterate
n/a	4	2	true	left	null	insert
3	4	4	true	left	2	iterate
n/a	4	2	false	right	null	insert
5	4	4	false	right	6	iterate
n/a	4	6	true	left	null	insert
7	4	4	false	right	6	iterate
n/a	4	6	false	right	null	insert

1. New node value
2. Root node value
3. Current node value
4. New node value < current node value?
5. New node should be inserted to left or right?
6. Value of node at insertion point
7. Result

Retrieving the minimum and maximum values from the BST

Two important implications of the insert() method are that:

• The minimum value in the BST is always the leftmost value in the BST.
• The maximum value in the BST is always the rightmost value in the BST.

Given these rules, defining methods to retrieve these values becomes fairly trivial.

Retrieving the minimum value

Let’s define a getMin() method for retrieving the minimum value from the BST:

class BST {
  ...
  getMin() {
    let current = this.root;
    while(current.left !== null) {
      current = current.left;
    }
    return current;
  }
}

The method can be called with a simple bst.getMin();. The following table illustrates the method’s inner workings:

Current node	Left node	Result
4	2	iterate
2	1	iterate
1	null	return

Retrieving the maximum value

Let’s now define a getMax() method for retrieving the maximum value from the BST:

class BST {
  ...
  getMax() {
    let current = this.root;
    while(current.right !== null) {
      current = current.right;
    }
    return current;
  }
}

This method can be called with a simple bst.getMax();. The following table illustrates the method’s inner workings:

Current node	Right node	Result
4	6	iterate
6	7	iterate
7	null	return

Finding a specific node in the BST

Finding a specific node in the BST is a matter of tracing a path through the BST until either a value is found that matches the requested value or a value of null is found, in which case it can be safely said that the BST does not contain the requested value. Following is the find() method McMillan defines, once again translated to ES6 from his ES5:

class BST {
  ...
  find(data) {
    let current = this.root;
    while (current.data !== data) {
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
      if (current === null) {
        return null;
      }
    }
    return current;
  }
}

Let’s try to find the node with a value of 3 by calling the method with bst.find(3);. Following is a table that illustrates the method’s inner workings. (A key to the column headings follows the table.)

1	2	3	4	5	6
4	false	true	left	2	iterate
2	false	false	right	3	iterate
3	true	n/a	n/a	n/a	return

1. Current node value
2. Is the current node value equal to the requested node value equal?
3. Is the requested node value less than the current node value?
4. Is the new current node to the left or right of the existing current node?
5. New current node value
6. Result

Conclusion

In this post we learned to differentiate between trees, binary trees and binary search trees (BSTs). We also created a BST using ES6 and added some methods to it for adding and retrieving data. Unfortunately we didn’t have time to cover some more advanced BST topics such as tree traversal and removing nodes–maybe this can be the subject of a future post.