Javascript — Implement Binary Search Tree

Motivation

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”

Linus Torvalds

Introduction

Tree

The tree is a linear data structure, order in a hierarchical manner. heavily used in any hierarchical system development, like:

File system, organizational profile

Binary Tree

The binary tree is the specific kind of tree where the maximum amount of children node is two.

Binary Search Tree

It is a binary tree where left nodes contain less value than the right nodes.

image credit: tutorials point

Common Term

Path = The specific way/nodes to access from one node to another.

Tree-Traversal = Visiting all nodes in a particular way.

root = First node of a Tree.

Key = Value of each node.

level = Specific break down of a tree.

Before move on

if you like proper documentation, please follow the below link.

DataDoc

And if you, like to see without the article itself, scroll down to the bottom and you will find the full code section.

Implementation

Before implementing a tree data structure, it is sagacious to understand javascript basic operations and methods.

Our binary search tree has some sub functionality.

1. Insert = insert data into node
2. Travers = traverse nodes for accessing values
3. Search = search within nodes
4. Remove = remove node/nodes

Basic structure

A Node object will contain all specific information of an individual node which accept 3 arguments dat, left, right.

Also a simple function show() will display value inside a node.

We also need a constructor function.

Insert

After finishing our basic structure, we are now prepared to insert some data into our tree.

Algorithm for insert operation:

1. root node === current node

2. if (datavalue in inserted node > datavalue of current node) set the new current node as left child, else skip step 4

3. if (left child value === null) insert the value and exit, else go on

4. current node == right child

5. if (value of right child === null ) insert new node and exit, else go on

Traverse

There are three kinds of traversing.

1. inOrder = Visit all the node in ascending order via node key value
2. preOrder = Will visit via node order (root => parent => children => left => right)
3. postOrder = Will visit (left child => root and then right child => root )

Search

There can be three types of searches in a binary search tree.

1. Min Value
2. Max Value
3. Specific Value

Min and max value searching are relatively easy, all min value can be found via traversing left nodes and max value can be found via traversing right node. Specific value searching is done via a comparison of all nodes.

Remove

Removing a node from a tree is way more complex than any other operation.

Removing a node without a child is easy, but removing a node with a child is complex. The safest way to do this operation is using recurssion

If the removed node is a leaf node, the parent node pointer should set as null.

If the removed node has one child that adjusts the pinter and if there are multiple children, then compare the value between children and adjust pointer accordingly.

A function will find the smallest value of a subtree, then use the value and delete the node.

That's it!

I know it is pretty much overflowed, but don't get too much bored, because knowing and implementing a binary search tree is really fun.

How to implement

Just copy-paste full code in a .js file and use it as a module.

Full Code

Thanks for your time.!