Insertion in a Binary in Level Order using JavaScript

Fig 1

In level order insertion node get inserted into the binary tree level by level. No node will be inserted into the next level until the last level is filled.

In Fig 1 we need to insert node 5. At levels 0 and 1, there are no vacant spaces. At level 2, node 2 doesn’t have any left children and node 3 does not have any children, but the first vacant space is the left child of node 2, so node 5 will be inserted as shown in fig 1.

We can initialise a tree as follows.

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

Tree consist of nodes, so we should have one node class.

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

Now, we need to create a method to insert nodes in tree.

If tree is not having any node then new node will be root.

insert(data){
if(this.root===null)
this.root= new Node(data)
}

Here this.root will refer to root of the tree because insert method is created inside tree class.

For level order traversal we will use queue data structure which is based on first in first out mechanism. Rest of the code is as follows.

insert(data) {
const q = [];
if (this.root === null) {
this.root = new Node(data);
} else {
q.push(this.root);
while (q.length !== 0) {
const node = q.shift();
if (node.left === null) {
node.left = new Node(data);
break;
} else {
q.push(node.left);
}
if (node.right === null) {
node.right = new Node(data);
break;
} else {
q.push(node.right);
}
}
}

If you are interested further reading about tree and how we can traverse tree you can go to below link.

Binary Tree Level Order Traversal or Breadth First Traversal

Thanks for reading :)