I'm trying to understand level order traversal of a tree using a queue. Here is my code (https://www.geeksforgeeks.org/level-order-tree-traversal/):
void printLevelOrder()
{
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count != 0) {
Node tempNode = queue.Dequeue();
Console.Write(tempNode.data " ");
if (tempNode.left != null) {
queue.Enqueue(tempNode.left);
}
if (tempNode.right != null) {
queue.Enqueue(tempNode.right);
}
}
}
How do I print nodes in a tree upto level n using a queue?
eg:
1 ------------------- Level 1
2 3 ------------------- Level 2
5 6 7 8 ----------------- Level 3
4 11 ------------------ Level 4
print nodes upto level 3?
CodePudding user response:
Associate each node with its level:
void printLevelOrder(int maxLevel)
{
var queue = new Queue<(Node node, int Level)>();
queue.Enqueue(root);
while (queue.Count != 0) {
var (tempNode, level) = queue.Dequeue();
if(level > maxLevel) return;
Console.Write(tempNode.data " ");
if (tempNode.left != null) {
queue.Enqueue((tempNode.left, level 1));
}
if (tempNode.right != null) {
queue.Enqueue((tempNode.right, level 1));
}
}
}
CodePudding user response:
If you want to print elements level-by-level you have to add one more extra constraint, before putting each element on queue; you need to check size of queue so that you can only dequeued i-th
element at a time where i
is the size of the queue and only enqueued each sub-trees i-th
elements.
void printLevelOrder(){
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count != 0) {
int size = queue.getSize();
list Array/LinkedList;
while(size-- > 0){
Node tempNode = queue.Dequeue();
list.add(tempNode.data);
if (tempNode.left != null) {
queue.Enqueue(tempNode.left);
}
if (tempNode.right != null) {
queue.Enqueue(tempNode.right);
}
}
print: list;
}
}
Note: please ignore syntax-error, and try to make the code in C#
.