Implementing Trees with NodeJS and Javascript

Trees

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;
  };

Jon, what is this __traverse thing here?

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!!

Where You Can Use/See it

File Systems Organization

Trees are used to model the structure of file systems, where each directory is a node that can contain direct files (nodes without children) or other directories (nodes with children).

Processamento e Busca de Dados

Binary search trees (BST), can help us store, search and sort data, with search, insertion and removal operations that, on average, have logarithmic execution time.

logarithmic?

This means that the execution time is faster than other solutions like sorting an array using basic functions, like bubble-sort for example.

Tips and Tricks

• When implementing trees, especially binary search trees, pay attention to keeping the tree balanced in order to optimize the performance of search, insertion and removal operations.
• Implement the traverse functions (such as in-order, pre-order and post-order) to explore stored data effectively.
• Consider using specialized tree structures such as AVL, Red-Black Trees, Tries for applications that require high efficiency in dynamic operations.

My Final Thoughts

Ao contrário do que muitos pensam (principalmente em algumas entrevistas por aí) eu não acho que você precisa saber implementar uma árvore de cabeça, do nada. Mas saber identificar e entender os conceitos base de como funciona uma estrutura de árvore, isso sim, faz sentido. Conseguimos utilizar Árvores em varios tipos de aplicações, de sistemas de arquivos a estruturas de dados dinâmicas, até sistemas de recomendação de produtos, etc, então é legal saber identificar quando estamos usando e quando podemos usar esse tipo de estrutura.

And You?!

Have you ever created/used something similar in your personal or company projects? Share your comments here with your questions, what you have already done, experiences, challenges, tips, etc!! Let's explore these concepts together, and if you see any bugs, errors, improvements, leave a comment as well!