Skip to main content

Level order traversal line by line using queue in typescript

Ts program for Level order traversal line by line using queue. Here problem description and other solutions.

/*
  TypeScript program for
  Level order traversal line by line
*/
// Binary Tree Node
class TreeNode
{
	public data: number;
	public left: TreeNode;
	public right: TreeNode;
	constructor(data: number)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Create Q node
class QNode
{
	public data: TreeNode;
	public next: QNode;
	public level: number;
	constructor(node: TreeNode)
	{
		this.data = node;
		this.next = null;
		this.level = 0;
	}
}
class MyQueue
{
	public head: QNode;
	public tail: QNode;
	public count: number;
	constructor()
	{
		this.head = null;
		this.tail = null;
		this.count = 0;
	}
	public number size()
	{
		return this.count;
	}
	public boolean isEmpty()
	{
		return this.count == 0;
	}
	// Add new node of queue
	public enqueue(value: TreeNode)
	{
		// 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;
			// Change node level
			node.level = this.head.level + 1;
		}
		this.count++;
		this.tail = node;
	}
	// Delete a element into queue
	public 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
	public TreeNode peek()
	{
		if (this.head == null)
		{
			return null;
		}
		return this.head.data;
	}
	// Level of head node
	public number peekLevel()
	{
		if (this.size() == 0)
		{
			return 0;
		}
		return this.head.level;
	}
}
class BinaryTree
{
	public root: TreeNode;
	constructor()
	{
		// Set initial tree root
		this.root = null;
	}
	public levelLineByLine()
	{
		if (this.root != null)
		{
			var q = new MyQueue();
			// Add first node
			q.enqueue(this.root);
			var node = this.root;
			var level = 0;
            var result = "";
			while (q.isEmpty() == false && node != null)
			{
				// Important to control new line
				if (q.peekLevel() != level)
				{
					// Add new line
					result += "\n";
				}
				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
				result +="  " + node.data;
				// Change level
				level = q.peekLevel();
				// Remove current node
				q.dequeue();
				// Get new head
				node = q.peek();
			}
          	console.log(result);
		}
		else
		{
			console.log("Empty Tree");
		}
	}
	public static main()
	{
		// Create new tree
		var tree = new BinaryTree();
		/*
		    Make A Binary Tree
		    -----------------------
		           1
		         /   \
		        2     3
		       /     / \
		      4     5   6
		     /  \    \    \
		    7     8   9    10
		*/
		// insert node of binary tree
		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.left.left.right = new TreeNode(8);
		tree.root.right.left.right = new TreeNode(9);
		tree.root.right.right.right = new TreeNode(10);
		// Display level order element
		tree.levelLineByLine();
	}
}
BinaryTree.main();
/*
 file : code.ts
 tsc --target es6 code.ts
 node code.js
 */

Output

  1
  2  3
  4  5  6
  7  8  9  10




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