Implementing Trees with NodeJS and Javascript

DOM, filesystems, nested menus — all trees: a root, children, no cycles (in theory). Foundation for BST (ep. 12), heaps (ep. 9), and tries (ep. 13).

What you'll learn:

• TreeNode with left / right
• Insert and search in a simple binary tree
• In-order, pre-order, post-order walks
• Tree vs nested JSON object

Prerequisites: queues (ep. 5).

Trees in JavaScript: left, right, and traversals

Trees are one of the most fundamental and powerful data structures, with trees we can organize data in a hierarchically. This type of structure can help us optimize data processing in general, from manipulating file systems to performing quick searches and also sorting.

Let's see the basic implementation of a tree in NodeJS/Javascript and the pros of using this structure.

Hands-on

First The Theory

The basic structure of a tree is made up of nodes, with a single node at the top (the root node). Each node can have child nodes, but only one parent, except the root, which has no parent. Seems like we are already complicating things up, right?

The depth of a node is measured by the number of edges between the node and the root. Trees are ideal for representing hierarchical relationships and for performing efficient searches and insertions.

Now The Practice

So the basic implementation of a Tree will start with a object that will represent the "nodes" and another object to represent the actual tree.

class TreeNode {
  constructor(value) {
    this.value = value
    this.left = null // left leaf
    this.right = null // right leaf
  }
}
 
class BinaryTree {
  constructor() {
    this.root = null
  }
 
  // Here we can put the functions to insert, print, etc
}

Now we can create the insert function:

  insert(value) {
    //check for params if needed
    const node = new TreeNode(value);
 
    if (this.root === null) {
      this.root = node;
    } else {
      let current = this.root;
 
      while (true) {
        if (value < current.value) {
          if (!current.left) {
            current.left = node;
            return this;
          }
 
          current = current.left;
        } else {
          if (!current.right) {
            current.right = node;
            return this;
          }
          current = current.right;
        }
      }
    }
  }

That's basically it. We have a tree with a insert function already working, one thing we can do now is "print" the tree values:

  print() {
    return console.log(JSON.stringify(this.__traverse(this.root)));
  }
 
  __traverse = (node) => {
    const tree = { value: node.value };
    tree.left = node.left === null ? null : this.__traverse(node.left);
    tree.right = node.right === null ? null : this.__traverse(node.right);
    return tree;
  };

What is this __traverse thing?

So, "traverse" is basically a function name, it represents the action of reading a node and getting to the next node, this "movement" from node A to node B is what we call traverse.

Now let's insert some values and run our Tree:

const tree = new BinaryTree()
tree.insert(9)
tree.insert(4)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
tree.insert(6)
tree.lookup(6)
tree.print()

If you done it right, you should be seeing something like:

{
  "value": 9,
  "left": {
    "value": 4,
    "left": { "value": 1, "left": null, "right": null },
    "right": { "value": 6, "left": null, "right": null }
  },
  "right": {
    "value": 20,
    "left": { "value": 15, "left": null, "right": null },
    "right": { "value": 170, "left": null, "right": null }
  }
}

A note here: we implemented a binary tree, so the elements that are bigger than the root node will go to the right, and the smaller ones to the left. There are other types of trees that we will explore in other posts, if you want a challange you can change to insert objects and see what happens!!

Edge cases: unbalanced trees and deep recursion

Inserting sorted data 1,2,3,... into a naive BST-shaped insert turns the tree into a linked list — O(n).

Deep recursive walks can hit Maximum call stack size exceeded — use an explicit stack for very tall trees.

TL;DR — Tree

Next steps

• Implementing Graphs
• Binary search trees

Before you go

Do you implement trees from scratch at work, or mostly recognise hierarchical problems? Report bugs in the JSON tree example if you find them.