Binary tree in Javascript

Let’s take a look at how a Binary Search Tree works and how they are implemented in Javascript.

Basics of tree structure

In a Binary tree there are three things one should know first:

Root : This is the top node of a tree structure and it does not have a parent. In the example image above, 8 is a Root node.
Parent : It’s a predecessor node, of a node. In the above example 3, 10, 6, 14 are parent nodes.
Child : It’s a successors of a parent node. In the above example 1 and 6 are children of 3 and so on.

Binary tree

In binary tree structure each node can have maximum of two children. Child on left subtree is called left child and child on right subtree is called right child.

Binary search tree

BST is a binary tree but with a few conditions:

1) All the keys (data inside the node) are distinct.
2) In every parent node, the left child key value is smaller than the parent node key value.
3) In every parent node, the right child key value is larger than the parent node key value.

Insertion of a node

For insertion of a new node with key value , a program will find the right place and it will create a new empty node for data. If the key value already exists, insertion will be declined and the insertion operation terminates immediately without insertion — as a BST is not allowed to have duplicate keys.

Binary Search Tree implementation in Javascript

	"use strict";
	class BinarySearchTree {
	constructor() {
	//initially root is null
	this.root = null;
	}
	insertNumberNode(data, left = null, right = null) {
	//creating a Node
	//data we pass will act as individual parent Node
	//left and right are subtrees
	let Node = {
	data,
	left,
	right
	};
	//suppose currentNumberNode as a parent node
	//current Num Node value decides position of next value
	//if it goes to left subtree or right subtree
	let currentNumberNode;
	if (!this.root) {
	//if its not a root make it one by passing a Node
	this.root = Node;
	} else {
	//and if its a root now, assign it to currentNumberNode
	currentNumberNode = this.root;
	while (currentNumberNode) {
	//if data is smaller than cuurent data, send it in left subtree
	if (data < currentNumberNode.data) {
	//if current num node don't have Node properties
	//we will assign it node properties
	if (!currentNumberNode.left) {
	currentNumberNode.left = Node;
	break;
	} else {
	//if it has node properties and it is sent by root to left
	//we will make it a left node because it is smaller than root node
	currentNumberNode = currentNumberNode.left;
	}
	//if data is larger than cuurent data, send it in right subtree
	} else if (data > currentNumberNode.data) {
	//if current num node don't have Node properties
	//we will assign it node properties
	if (!currentNumberNode.right) {
	currentNumberNode.right = Node;
	break;
	} else {
	//if it has node properties and it is sent by root to right
	//we will make it a right node because it is larger than root node
	currentNumberNode = currentNumberNode.right;
	}
	} else {
	console.log("Try Different Value");
	break;
	}
	}
	}
	}
	}
	let BSTtest = new BinarySearchTree();
	//tests
	BSTtest.insertNumberNode(10);
	BSTtest.insertNumberNode(7);
	BSTtest.insertNumberNode(14);
	BSTtest.insertNumberNode(5);
	BSTtest.insertNumberNode(13);
	BSTtest.insertNumberNode(8);
	BSTtest.insertNumberNode(18);
	BSTtest.insertNumberNode(15);
	BSTtest.insertNumberNode(6);
	BSTtest;

view raw BST.js hosted with ❤ by GitHub

And that’s it! 🎉

If you like this article let me know in comments or tweet about it.

(you can also read this on Medium )