Data Structures: Trees II

This is part 2 of the article on Tree data structures. In the first part of this article, we looked at the types of trees, how they work, and their uses. In this part, we are going to implement a Binary Search Tree (BST) and General Tree using Javascript.

Before we get into the coding aspect, we need to first address two very important concepts Recursion and Tree Traversal.

Recursion

Recursion is when a function solves a problem by repeatedly calling itself. Recursion is used in algorithms where the amount of data we are working with is unknown. Recursion involves solving a problem by repeatedly solving small parts of the problem until the complete problem is solved. A good analogy for recursion is this one given by Aaron Krolik on Quora

Someone in a movie theatre asks you what row you're sitting in. You don't want to count, so you ask the person in front of you what row they are sitting in, knowing that you will respond with one greater than their answer. The person in front will ask the person in front of them. This will keep happening until word reaches the front row, and it is easy to respond: "I'm in row 1!" From there, the correct message (incremented by 1 each row) will eventually make its way back to the person who asked.

The reason why we need to understand recursion before making our tree data structures is that some of the methods are easier and faster to write recursively because trees can have anything from just a few to thousands of nodes.

An example of a recursive function is this addAll(n) function that adds all numbers that are less than a given number to said number.

function addAll(n){
    if(n === 1){ 
        return 1; 
    } 
    else { 
        return n + addAll(n - 1) //recursion.
     } 
}

When the above function is called it first checks if the value of n is 1 and returns it; if true, this is known as the base case and is the condition that ends the function. if n is greater than 1, then the function adds n to the result of calling itself again. Most languages make use of the call stack or stack frame to keep track of the order in which the function calls itself.

Tree Traversal

Tree traversal refers to the process of searching and accessing nodes in a tree. Trees do not have direct access, so we use algorithms to locate and access nodes in a tree. Tree traversal algorithms ensure that nodes in a tree are only visited once (data is only accessed once) when searching through a tree. There are 2 main categories of tree traversal algorithms Depth-First Search (DFS) and Breadth-First Search (BFS) also known as Level Order Traversal.

DFS: DFS algorithms work in a branch-by-branch manner, meaning they visit each subtree in a tree and their subtrees in turn. The name Depth first refers to how the algorithms go from the deepest leaf node in a subtree and back to the root for each child of the root node.

There are 3 main types of Depth First Traversal algorithms:

• Inorder Traversal: This is when the subtrees of a tree are visited from the left-most node to the root and then the right-most node. In-order traversal algorithms follow a left, root and then right approach when traversing the tree; we can see this in action below.

• Preorder Traversal: In this type of algorithm the root node is visited first, then from the left-most subtree (and its subtrees) to the right-most subtree (and its subtrees).

• Postorder Traversal: In this type of algorithm, all sub-trees starting from the left, and going to the right are visited before the root node.

BFS: BFS, also known as level-order traversal, is when nodes in a tree are visited level-by-level. In the algorithm, a queue is used to keep track of the nodes in a tree and ensure they are visited in a FIFO (first in, first-out) manner. A level order traversal would look like this in action.

Both the BFS and DFS are algorithms used in graph data structures which we shall cover in the future, trees are considered a form of a graph. Now that we have an understanding of recursion and traversal, we can start building our Trees.

General Tree In Javascript

The first tree we will be building is a general tree and we will be using a linked list to keep track of the child nodes of each node.

Our general tree is going to have 4 main methods:

• Insert: This method adds a node to the tree.
• Contains: This method checks if data is present in a tree.
• Print: This function prints the value of each node in the tree using a level order traversal.
• Size: This function returns the number of nodes in the tree.

First, let's create a node with 3 properties; the value of the node; a linked list of children, and a pointer to the next sibling node.

class Node {
  constructor (data) {
    this.value = data;
    this.children = new LinkedList();
    this.next = null;
  }
}

The linked list is going to have 3 properties, the pointers for the head and tail of the list, and a size property to keep track of the size of the linked list. The linked list will have a method called append to add a new node to the list.

class LinkedList {
  constructor() {
    (this.head = this.tail = null), (this.size = 0);
  }

  append (node) {
    if (!this.tail) {
      this.tail = node;
      this.head = this.tail;
    } else {
      let oldTail = this.tail;
      this.tail = node;
      oldTail.next = this.tail;
    }
    this.size++;
  }

}

Our Tree will have 2 properties; a pointer to the root node of the tree, and a count of the nodes in the tree.

class Tree {
  constructor() {
    this.root = null;
    this.count = 0;
  }
}

A few of our tree methods will require us to use traversal to find a node, so let's make a traversal method first.

Method break down

• Create an array called queue and push the root node into the array,
• Create a currentNode variable but leave it undefined.
• Initializes a while loop that will run as long as there is a value in the queue array.
• Inside the loop, remove and set the head of the queue array to currentNode.
• If currentNode has children then we push them to the queue as well using a while loop.
• Else we check if currentNode is the node we are looking for; if yes, return it and end the function, otherwise we keep looping through the tree till we find it.
• if we don't find it, we return false.

The function should look like below.

bfsFindNode(data) {
    let queue = [];
    queue.push(this.root);
    let currentNode;

    while (queue.length > 0) {
      node = queue.shift();
      if (node.children.size > 0) {
        let currentChild = node.children.head;
        while (currentChild) {
          queue.push(currentChild);
          currentChild = currentChild.next;
        }
      }

      if (currentNode.value === data) {
        return node;
      }
    }
    return false;
  }

Insert Method

The insert method adds a node into the tree under a specified parent node.

Method Break Down

• Create a new node using the given data as the value.
• Create an undefined variable called parentNode.
• Check if we have a root node; if no, set the new node as the root, increase the count by 1, and end the method.
• If we have a root node check that a parent value is specified; if not, let the user know and end the function.
• If yes, search for it using our previously created bfsFindNode method.
• if the node is present, append the new node to its children's linked list; if not, let the user know the node does not exist in the tree.

The function should look like the below.

  insert(data, parent) {
    let node = new Node(data);
    let parentNode;
    if (!this.root) {
      this.root = node;
      this.count++;
      return;
    }

    if (!parent) {
      console.log("please specify a parent");
      return;
    }

    parentNode = this.bfsFindNode(parent);

    if (!parentNode) {
      console.log("that node does not exist");
      return;
    }

    parentNode.children.append(node);
    this.count++;
  }

Contains Method

The contains method checks if a node is present in a tree or not and returns true or false.

  contains(data) {
     if(data){
      let parentNode = this.bfsFindNode(data);
      if (parentNode) {
        return true;
      }
      return false;  }
  }

Size Method

The size method returns the count property of the tree, which tells us how many nodes are in the tree.

  size() {
    console.log(this.count);
    return this.count;

  }

Print Method

The print method uses the same logic as our bfsFindNode method; the only difference is that it logs each node to the console as it traverses through the tree.

 print() {
    if (this.count) {
      let queue = [];
      queue.push(this.root);
      let node;
      while (queue.length > 0) {
        node = queue.shift();
        if (node.children.size > 0) {
          let currentNode = node.children.head;
          while (currentNode) {
            queue.push(currentNode);
            currentNode = currentNode.next;
          }
        }
        console.log(node.value);
      }
    }
  }

Complete General Tree Code

class Node {
  constructor(data) {
    this.value = data;
    this.children = new LinkedList();
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    (this.head = this.tail = null), (this.size = 0);
  }

  append(node) {
    if (!this.tail) {
      this.tail = node;
      this.head = this.tail;
    } else {
      let oldTail = this.tail;
      this.tail = node;
      oldTail.next = this.tail;
    }
    this.size++;
  }

}

class Tree {
  constructor() {
    this.root = null;
    this.count = 0;
  }

  bfsFindNode(data) {
    let queue = [];
    queue.push(this.root);
    let node;

    while (queue.length > 0) {
      node = queue.shift();
      if (node.children.size > 0) {
        let currentNode = node.children.head;
        while (currentNode) {
          queue.push(currentNode);
          currentNode = currentNode.next;
        }
      }

      if (node.value === data) {
        return node;
      }
    }
    return false;
  }

  insert(data, parent) {
    let node = new Node(data);
    let parentNode;
    if (!this.root) {
      this.root = node;
      this.count++;
      return;
    }

    if (!parent) {
      console.log("please specify a parent");
      return;
    }

    parentNode = this.bfsFindNode(parent);

    if (!parentNode) {
      console.log("that node does not exist");
      return;
    }

    parentNode.children.append(node);
    this.count++;
  }

  contains(data) {
      let parentNode = this.bfsFindNode(data);
      if (parentNode) {
        return true;
      }
      return false;
  }

  print() {
    if (this.count) {
      let queue = [];
      queue.push(this.root);
      let node;
      while (queue.length > 0) {
        node = queue.shift();
        if (node.children.size > 0) {
          let currentNode = node.children.head;
          while (currentNode) {
            queue.push(currentNode);
            currentNode = currentNode.next;
          }
        }
        console.log(node.value);
      }
    }
  }

  size() {
    console.log(this.count);
    return this.count;
  }
}

You can find the code here, try adding some of your own methods.

Binary Search Tree In Javascript

Our BST is going to have 5 methods:

• Insert: Adds a node to the tree.
• Min: Returns the lowest value in the tree.
• Max: Returns the highest value in a tree.
• Print: Prints all the nodes in the tree.
• Size: The number of nodes in the tree.

In this tree we won't be needing a linked list because BSTs have a finite amount of children per node, 2 to be exact, usually called left and right. The left node always has a lesser value than its parent, while the right node has a higher value.

The BST nodes will have 3 properties, a value, and 2-pointers to the left and right child nodes. while our tree will have 2 same as before.

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

  }
}

class Tree {
  constructor() {
    this.root = null;
    this.count = 0;

  }
}

Insert Method

The insert method will make use of a recursive function to search through the tree. I will be using the preorder traversal method.

Method Break Down

• Check that the given data is a number; if not, let the user know.
• Create a new node using the given number.
• Check if the tree is empty; if it is, set the new node as the root of the tree.
• If the tree is not empty, then we will have to compare the given data to each node in the tree starting from the root to find a parent for the data.
• First, we check if the root data is equal to the root; if it is; then let the user know that the node already exists.
• If the data is not equal to the root, we will check if the data is less than or greater than the root node;
• If it is less, and the left pointer is null, we can set the new node as the left child of the root.
• If the data is greater than the root and the right pointer is null, we can set the new node as the right child of the root.
• If the left pointer is occupied we will repeat the process again, using the left child as the root.
• If the right pointer is occupied we will repeat the process again, using the right child as the root.

  insert(data) {
    if (typeof data === "number") {
      let newNode = new Node(data);

      if (!this.root) {
        this.root = newNode;
        this.count++;
        return;
      }

      let dftSearch = (node) => {
        // check root
        if (data === node.value) {
          console.log("node already exist");
          return;
        }

        // check left
        if (data < node.value) {
          if (node.left) {
            dftSearch(node.left);
          } else {
            node.left = newNode;
            this.count++;
          }
        }

        // check right
        if (data > node.value) {
          if (node.right) {
            dftSearch(node.right);
          } else {
            node.right = newNode;
            this.count++;
          }
        }
      };

      dftSearch(this.root);
    }
  }

Min Method

The min method simply returns the lowest value in the tree; this means all we have to do is traverse left down the tree till we reach the last leaf node.

  min() {

    let currentNode = this.root;
    while (currentNode.left) {
      currentNode = currentNode.left;
    }

    console.log(currentNode.value);
    return currentNode.value;
  }

Max Method

The Max Method returns the highest value in the tree, similar to the min method; the difference being we go right instead of left.

  max() {
    let currentNode = this.root;
    while (currentNode.right) {
      currentNode = currentNode.right;
    }

    console.log(currentNode.value);
    return currentNode.value;
  }

Print Method

The print method traverses the whole tree in a preorder manner and prints the value of each node. The method uses a recursive function to do this.

Method Break Down

• Starting from root, we log the value of the node to the console.
• Check for a left child.
• Check for a right child.
• If left child is present, call function with left child as root.
• If right child is present, call function with right child as root.

  print() {
    let dftPrint = (node) => {
      // check root
      console.log(node.value);

      // check left
      if (node.left) {
        dftPrint(node.left);
      }

      // check right
      if (node.right) {
        dftPrint(node.right);
      }
    };

    dftPrint(this.root);
  }

Size Method

The method simply logs the number of nodes in the tree to the console.

  size() {
    console.log(this.count);
    return this.count;
  }

Complete Binary Search Tree Code

class Node {

  constructor(data) {
    this.value = data;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor() {
    this.root = null;
    this.count = 0;
  }

  insert(data) {
    if (typeof data === "number") {
      let newNode = new Node(data);

      if (!this.root) {
        this.root = newNode;
        this.count++;
        return;
      }

      let dftSearch = (node) => {
        // check root
        if (data === node.value) {
          console.log("node already exist");
          return;
        }

        // check left
        if (data < node.value) {
          if (node.left) {
            dftSearch(node.left);
          } else {
            node.left = newNode;
            this.count++;
          }
        }

        // check right
        if (data > node.value) {
          if (node.right) {
            dftSearch(node.right);
          } else {
            node.right = newNode;
            this.count++;
          }
        }
      };

      dftSearch(this.root);
    }
  }

  min() {
    let currentNode = this.root;
    while (currentNode.left) {
      currentNode = currentNode.left;
    }

    console.log(currentNode.value);
    return currentNode.value;
  }

  max() {
    let currentNode = this.root;
    while (currentNode.right) {
      currentNode = currentNode.right;
    }

    console.log(currentNode.value);
    return currentNode.value;
  }

  print() {
    let dftPrint = (node) => {
      // check root
      console.log(node.value);

      // check left
      if (node.left) {
        dftPrint(node.left);
      }

      // check right
      if (node.right) {
        dftPrint(node.right);
      }
    };

    dftPrint(this.root);
  }

  size() {
    console.log(this.count);
    return this.count;
  }
}

You can find the code here

If this article was helpful please give it a :heart: i would really appreciate it.