Question

Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on. You must do this in linear time. Prove your time bound (Java)

Answer 1

/*If you have any query do comment in the comment section else like the solution*/

This can be done using a FIFO queue, in which left and right child of a parent node will be pushed in the queue, each node will be pushed and popped from the queue only once, hence the time complexity will be O(n)

void levelOrderTraversal(Node root) 
{     
    if(root == null) 
        return;       
    Queue<Node> q =new LinkedList<Node>();       
    q.add(root);                    
    while(q.size() > 0) 
    {                                   
        Node node = q.peek(); 
        q.remove();
        System.out.print(node.data + " ");            
        if(node.lt != null) 
            q.add(node.lt); 
        if(node.rt != null) 
            q.add(node.rt);                       
    } 
}