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 theater 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 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 because 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 subtrees starting from the left, 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 both algorithms used in graph data structures which we shall cover in the future, trees are considered a form of 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 a 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 lets 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 lets 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 other wise 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 linked list; if not, let the user know the node does not exist in the tree.
The function should look like 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 being 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 the number of nodes in the tree.
In this tree we won't be needing a linked list because BST's 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 it's 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 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 the 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 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 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 root.
- If the left pointer is occupied we will repeat the process again, using the left child as root.
- If the right pointer is occupied we will repeat the process again, using the right child as 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 ❤️ i would really appreciate it.
Top comments (0)