#Author	:	Bhavya Singh
#Date	:	23-May-2020
#Name	:	Level Order Traversal


#PROBLEM:

You are given a tree and you need to do the level order traversal on this tree.
Level order traversal of a tree is breadth-first traversal for the tree.



Level order traversal of above tree is 1 2 3 4 5

Input:
First line of input contains the number of test cases T. For each test case, there will be only a single line of input which is a string representing the tree as described below: 

The values in the string are in the order of level order traversal of the tree where, numbers denotes node values, and a character “N” denotes NULL child.

For example:

For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N

Output:
The function should print the level order traversal of the tree as specified in the problem statement.

Your Task:
You don't have to take any input. Just complete the function levelOrder() that takes node as parameter and prints the level order. The newline is automatically appended by the driver code.

Constraints:
1 <= T <= 100
1 <= Number of nodes<= 104
1 <= Data of a node <= 104

Example:
Input:
2
1 3 2
10 20 30 40 60 N N
Output:
1 3 2
10 20 30 40 60

Explanation:
Testcase1: The tree is
        1
     /      \
   3       2
So, the level order would be 1 3 2
Testcase2: The tree is
                           10
                        /        \
                     20         30
                  /       \
               40       60
So, the level order would be 10 20 30 40 60

#CODE

"""
class Node:
    def __init__(self, value):
        self.left = None
        self.data = value
        self.right = None
"""
# Your task is to complete this function
# Function should print the level order of the tree in required format
# only input to function is the root of the tree
def levelOrder( root ):
    
    #Base case
    if root is None:
        return
    
    #empty queue
    queue = []
    
    #enqueue root and initialize height
    queue.append( root )
    
    while( len(queue) > 0 ):
        
        #print front of queue and remove from queue
        print( queue[0].data, end = " " )
        node = queue.pop( 0 )
        
        #enqueue left child
        if node.left is not None:
            queue.append( node.left )
        
        #enqueue right child
        if node.right is not None:
            queue.append( node.right )