Skip to main content

Level order traversal using queue in kotlin

Kotlin program for Level order traversal using queue. Here more information.

/*
  Kotlin program for
  Level order tree traversal using queue
*/
// Create Q node
class QNode
{
	var data: TreeNode ? ;
	var next: QNode ? ;
	constructor(node: TreeNode ? )
	{
		this.data = node;
		this.next = null;
	}
}
// Binary Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class MyQueue
{
	var head: QNode ? ;
	var tail: QNode ? ;
	var count: Int;
	constructor()
	{
		this.head = null;
		this.tail = null;
		this.count = 0;
	}
	fun size(): Int
	{
		return this.count;
	}
	fun isEmpty(): Boolean
	{
		return this.count == 0;
	}
	// Add new node of queue
	fun enqueue(value: TreeNode ? ): Unit
	{
		// Create a new node
		val node: QNode = 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 += 1;
		this.tail = node;
	}
	// Delete a element into queue
	fun dequeue(): Unit
	{
		if (this.head == null)
		{
			// Empty Queue
			return;
		}
		// Visit next node
		this.head = this.head?.next;
		this.count -= 1;
		if (this.head == null)
		{
			// When deleting a last node of linked list
			this.tail = null;
		}
	}
	// Get front node
	fun peek(): TreeNode ?
	{
		if (this.head == null)
		{
			return null;
		}
		return this.head?.data;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	fun levelOrder(): Unit
	{
		if (this.root != null)
		{
			val q: MyQueue = MyQueue();
			// Add first node
			q.enqueue(this.root);
			var node: TreeNode ? = 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
				print("  " + node.data);
				// Remove current node
				q.dequeue();
				// Get new head
				node = q.peek();
			}
		}
		else
		{
			println("Empty Tree");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new tree
	val tree: BinaryTree = BinaryTree();
	/*
	  Make A Binary Tree
	  -----------------------
	         1
	       /   \
	      2     3
	     /     / \
	    4     5   6
	   /     / \
	  7     8   9
	*/
	// Adding tree nodes
	tree.root = TreeNode(1);
	tree.root?.left = TreeNode(2);
	tree.root?.right = TreeNode(3);
	tree.root?.right?.right = TreeNode(6);
	tree.root?.right?.left = TreeNode(5);
	tree.root?.left?.left = TreeNode(4);
	tree.root?.left?.left?.left = TreeNode(7);
	tree.root?.right?.left?.left = TreeNode(8);
	tree.root?.right?.left?.right = TreeNode(9);
	// Display level order  element
	tree.levelOrder();
}

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