Binary Tree Level Order Traversal

Given a serialized binary tree in level order with null values representing missing nodes, reconstruct the binary tree and output its level order traversal. Each node's value is a single-digit integer (0-9).

The serialization is provided as a comma-separated string where the keyword null indicates that a node is missing. For example, the serialized tree 1,2,null,null,3,4,null,null,5,null,null corresponds to the level order traversal [1, 2, 3, 4, 5].

Please note that the tree is constructed in level order: the first value is the root, and subsequent pairs of values (or nulls) represent the left and right children of each node in order.

inputFormat

The first line of input contains an integer t representing the number of test cases.

Each of the following t lines contains a comma-separated string representing the serialized binary tree. The token null indicates a missing node.

outputFormat

For each test case, output a single line which contains the level order traversal of the binary tree. The values must be printed as space-separated integers. If the tree is empty, print an empty line.

2
1,2,null,null,3,4,null,null,5,null,null
1,null,2,null,3,null,4,null,5,null,null

1 2 3 4 5
1 2 3 4 5