Implementing a Tree in JavaScript

As I do more algorithm questions to prepare for interviews, I am learning more about different datatypes and ways to store data. One such question on LeetCode asked to traverse a tree. I didn’t know what it was so did some research, and this is what I found.

Tree Data Structures in JavaScript for Beginners

A tree look somewhat like this theoretically:

A tree node has a value and links, called edges, to its parent and descendents or children.

Let’s create a TreeNode from scratch in JavaScript.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.descendents = [];
  }
}

Now that we can create and initialize TreeNodes, let’s try creating a tree.

// create nodes with values
const abe = new TreeNode('Abe');
const homer = new TreeNode('Homer');
const bart = new TreeNode('Bart');
const lisa = new TreeNode('Lisa');
const maggie = new TreeNode('Maggie');
// associate root with is descendents
abe.descendents.push(homer);
homer.descendents.push(bart, lisa, maggie);

This will create the following tree:

The next step is to allow trees to have left and right nodes:

const LEFT = 0;
const RIGHT = 1;
class TreeNode {
  constructor(value) {
    this.value = value;
    this.descendents = [];
    this.parent = null;
  }
get left() {
    return this.descendents[LEFT];
  }
set left(node) {
    this.descendents[LEFT] = node;
    if (node) {
      node.parent = this;
    }
  }
get right() {
    return this.descendents[RIGHT];
  }
set right(node) {
    this.descendents[RIGHT] = node;
    if (node) {
      node.parent = this;
    }
  }
}

To insert nodes, this graphic from the tutorial really helped. We are inserting 30, 40, 10, 15, 12, 50.

1. If the tree is empty, the first node becomes the root and you’re done.

2. Compare the root/parent’s value. If it’s higher, go right. If it’s lower, go left. If it’s the same, then the value already exists to increase the duplicate count, known as multiplicity.

3. Repeat step 2 until there is an empty slot to insert the node.

This is called a binary search tree.

This seems to be a common algorithm question.

Happy coding!