Level Order Traversal
The below function requires a queue data structure of type pointer to Node to be created and initialised.
void levelOrder(struct Node *ptr) {
// Queue structure to store pointer
struct Queue q;
// Print the root node as it is on the topmost level
printf("%d\t", ptr -> data);
// Enqueue root node to the queue
enqueue(&q, ptr);
while (!isEmpty(q)) {
// Obtain root of subtree
ptr = dequeue(&q);
// Print & enqueue the left child of next level if present
if (ptr -> left) {
printf("%d\t", ptr -> left -> data);
enqueue(&q, ptr -> left);
}
// Print & enqueue the left child of next level if present
if (ptr -> right) {
printf("%d\t", ptr -> right -> data);
enqueue(&q, ptr -> right);
}
}
}
Contributed by Nitin Ranganath