Level order traversal using queue in node js

Js program for Level order traversal using queue. Here problem description and explanation.

/*
  Node JS program for
  Level order tree traversal using queue
*/
// Create Q node
class QNode
{
	constructor(node)
	{
		this.data = node;
		this.next = null;
	}
}
// Binary Tree Node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class MyQueue
{
	constructor()
	{
		this.head = null;
		this.tail = null;
		this.count = 0;
	}
	size()
	{
		return this.count;
	}
	isEmpty()
	{
		return this.count == 0;
	}
	// Add new node of queue
	enqueue(value)
	{
		// Create a new node
		var node = new QNode(value);
		if (this.head == null)
		{
			// Add first element into queue
			this.head = node;
		}
		else
		{
			// Add node at the end using tail
			this.tail.next = node;
		}
		this.count++;
		this.tail = node;
	}
	// Delete a element into queue
	dequeue()
	{
		if (this.head == null)
		{
			// Empty Queue
			return;
		}
		// Visit next node
		this.head = this.head.next;
		this.count--;
		if (this.head == null)
		{
			// When deleting a last node of linked list
			this.tail = null;
		}
	}
	// Get front node
	peek()
	{
		if (this.head == null)
		{
			return null;
		}
		return this.head.data;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	levelOrder()
	{
		if (this.root != null)
		{
			var q = new MyQueue();
			// Add first node
			q.enqueue(this.root);
			var node = this.root;
			while (q.isEmpty() == false && node != null)
			{
				if (node.left != null)
				{
					// Add left child node
					q.enqueue(node.left);
				}
				if (node.right != null)
				{
					// Add right child node
					q.enqueue(node.right);
				}
				// Display level node
				process.stdout.write("  " + node.data);
				// Remove current node
				q.dequeue();
				// Get new head
				node = q.peek();
			}
		}
		else
		{
			console.log("Empty Tree");
		}
	}
}

function main()
{
	// Create new tree
	var tree = new BinaryTree();
	/*
	  Make A Binary Tree
	  -----------------------
	         1
	       /   \
	      2     3
	     /     / \
	    4     5   6
	   /     / \
	  7     8   9
	*/
	// Adding tree nodes
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(2);
	tree.root.right = new TreeNode(3);
	tree.root.right.right = new TreeNode(6);
	tree.root.right.left = new TreeNode(5);
	tree.root.left.left = new TreeNode(4);
	tree.root.left.left.left = new TreeNode(7);
	tree.root.right.left.left = new TreeNode(8);
	tree.root.right.left.right = new TreeNode(9);
	// Display level order  element
	tree.levelOrder();
}
// Start program execution
main();

Output

  1  2  3  4  5  6  7  8  9



Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2022, kalkicode.com, All rights reserved