Level Order Traversal of this tree would be
1 2 3 4 5 6
Approach:
Starting from the root, first the node is visited and printed then it’s child nodes are put in a queue.
struct node { int value; struct node* left; struct node* right; }; void levelOrderTraversal(struct node *root) { struct node *queue[100] = {(struct node *)0}; int size = 0; int queue_pointer = 0; struct node *temp = root; while(temp) { printf("%d", temp->value); if(temp->left) { queue[size++] = temp->left; } if(temp->right) { queue[size++] = temp->right; } temp = queue[queue_pointer++]; } }
Time Complexity:
As we are visiting each node once.So the time complexity would be O(n) where n is the number of nodes in the tree.
Pingback: Recursive Level Order Traversal of a tree | CrazyForCode
//Java Implementation
public static void printLevel(Node root) {
if(root==null)
{
return;
}
Queuequeue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty())
{
Node temp = queue.poll();
System.out.print(temp.getData());
if(temp.getLeft()!=null)
{
queue.offer(temp.getLeft());
}
if(temp.getRight()!=null)
{
queue.offer(temp.getRight());
}
}
}