Level order traversal using queue in c#

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

// Include namespace system
using System;
/*
  Csharp program for
  Level order tree traversal using queue
*/
// Create Q node
public class QNode
{
	public TreeNode data;
	public QNode next;
	public QNode(TreeNode node)
	{
		this.data = node;
		this.next = null;
	}
}
// Binary Tree Node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class MyQueue
{
	public QNode head;
	public QNode tail;
	public int count;
	public MyQueue()
	{
		this.head = null;
		this.tail = null;
		this.count = 0;
	}
	public int size()
	{
		return this.count;
	}
	public bool isEmpty()
	{
		return this.count == 0;
	}
	// Add new node of queue
	public void enqueue(TreeNode 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
	public void 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;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set initial tree root
		this.root = null;
	}
	public void 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
				Console.Write(" {0} ", node.data);
				// Remove current node
				q.dequeue();
				// Get new head
				node = q.peek();
			}
		}
		else
		{
			Console.WriteLine("Empty Tree");
		}
	}
	public static void Main(String[] args)
	{
		// 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();
	}
}

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