Level order traversal line by line using queue in c#
Csharp program for Level order traversal line by line using queue. Here problem description and explanation.
// Include namespace system
using System;
/*
Csharp program for
Level order traversal line by line
*/
// 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;
}
}
// Create Q node
public class QNode
{
public TreeNode data;
public QNode next;
public int level;
public QNode(TreeNode node)
{
this.data = node;
this.next = null;
this.level = 0;
}
}
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;
// Change node level
node.level = this.head.level + 1;
}
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;
}
// Level of head node
public int peekLevel()
{
if (this.size() == 0)
{
return 0;
}
return this.head.level;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root
this.root = null;
}
public void levelLineByLine()
{
if (this.root != null)
{
var q = new MyQueue();
// Add first node
q.enqueue(this.root);
var node = this.root;
var level = 0;
while (q.isEmpty() == false && node != null)
{
// Important to control new line
if (q.peekLevel() != level)
{
// Add new line
Console.WriteLine();
}
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(" " + node.data.ToString());
// Change level
level = q.peekLevel();
// 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 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();
}
}
Output
1
2 3
4 5 6
7 8 9 10
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