Binary Search Tree in JavaScript - (Implementation, Traversing, Formulas)

A picture taken from google

When one talks about Data Structures, a Tree is the most fascinating data structure among all others. Such an amazing concept has its own pros and cons, still is one of the most used data structure in the world of programming — from Indexing in databases to searching and sorting it never leaves a developers hand in any aspect of life.

One of the most used type of Tree is the Binary Search Tree(BST).

In this article we will discuss the following things:

1. What a typical BST looks like and some rules.
2. Ways of implementing a BST and implementing it in JS.
3. Formulas of BST.
4. Traversing a BST (In-order, Pre-order, Post-order).

A Typical BST:

Representation of a Binary Search Tree

As shown in the image above, a BST consists of one Root node, Internal nodes/Parent nodes and External/ Leaf nodes.

Each node in a BST can at most contain 2 child nodes — one left child and one right child.

In the Image above the tree is color coded as Red: Root, Green: Left child, Yellow: Right child.

Level of the tree is the number of levels from the leaf node to the root node. Depth of the tree is same as the Height of the tree which is the largest number of edges from the root nodes to the most distant leaf node.

Ways of implementing a BST:

BST can be represented either as an array or a linked list. When we use an array to make a BST, all the nodes are stored in linear order where the index of the node in array is the same as the index in BST. Thus, whenever a parent node has only one node/ places where there are empty nodes, that position of the array remains empty. So the memory is blocked and is not used. Hence, an array is not the best option for implementing a BST.

When we use a linked list, no memory is blocked irrespective of the size of the BST and the number of children each node has.

BST Implementation using Linked List:

Let’s have a look on how this BST can be illustrated.

Illustration of a BST implemented using Linked List

Formulas:

Index of left child = 2n+1 (Where n is the index of the parent)

Index of right child = 2n+2 (Where n is the index of the parent)

Index of left sibling = n-1 (where n is the index of current/ right node)

Index of right node = n+1 (where n is the index of current/ left node)

Father = floor of (n-1)/2 (where n is the index of the current/ child node)

Traversing a BST:

There are three ways in which we can traverse a BST — In-order, Pre-Order, Post-order.

In-order — Left Node > Root > Right Node. The In-order traversal for diagram-1 is 10, 20, 50, 52, 55, 60, 65 (It arranges in ascending order)

Pre-order — Root > Left Node > Right Node. The Pre-order traversal for diagram-1 is 50, 20, 10, 55, 52, 60, 65.

Post-order — Left Node >Right Node > Root. The Post-order traversal for diagram-1 is 10, 20, 52, 65, 60, 55, 50.

Now let’s code it:

Thanks for reading. Drop a like to motivate me to write more such articles and your helpful feedbacks are always welcome in the comments.

Have a great day!