# 1466 - Percurso em Árvore por Nível
- **ID**: 1466
- **IdBecrowd**: 1466
- **Tags**: estruturas-dados, grafos
- **Nível**: 3
- **Tempo Limite**: 2 segundos
- **Memória**: 200 MB
- **Categoria**: Grafos
- **Autor**: Por Neilor Tonin, URI  Brasil

## Descrição
Em uma árvore binária, o percurso por nível é um percurso denominado breadth first search (BFS) ou em português, busca em largura, a qual seria não-recursiva por natureza. Este percurso utiliza uma fila ao invés de pilha para armazenar os próximos 2 nodos que devem ser pesquisados (filho à esquerda e à direita). Esta é a razão pela qual você deve percorrer os nodos na ordem FIFO ao invés da ordem LIFO, obtendo desta forma a recursão.

Portanto nossa tarefa aqui, após algumas operações de inserção sobre uma árvore binária de busca (pesquisa), é imprimir o percurso por nível sobre estes nodos. Por exemplo, uma entrada com a sequência de valores inteiros: 8 3 10 14 6 4 13 7 1 resultará na seguinte árvore:

![](assets/images/0a6bb2_UOJ_1466.png)

Com a saída de uma listagem por nível: 8 3 10 1 6 14 4 7 13.

## Entrada
A entrada contém vários casos de teste. A primeira linha da entrada contém um inteiro 
C
 (
C
 ≤ 1000), indicando o número de casos de teste que virão a seguir. Cada caso de teste é composto por 2 linhas. A primeira linha contém um inteiro 
N
 (1 ≤ 
N
 ≤ 500) que indica a quantidade de números que deve compor cada árvore e a segunda linha contém 
N
 inteiros distintos e não negativos, separados por um espaço em branco.

## Saída
Para cada caso de teste de entrada você deverá imprimir a mensagem "Case 
n
:", onde 
n
 indica o número do caso de teste seguido por uma linha contendo a listagem por nível dos nodos da árvore, conforme o exemplo abaixo. 
Obs: Não deve haver espaço em branco após o último item de cada linha e há uma linha em branco após cada caso de teste, inclusive após o último. A árvore resultante não terá nodos repetidos e também não terá mais do que 500 níveis.

## Exemplos
### Exemplo de Entrada
```
Sample Input
```

### Exemplo de Saída
```
Sample Output
```

### Exemplo de Entrada
```
2

                                3

                                5 2 7

                                9

                                8 3 10 14 6 4 13 7 1
```

### Exemplo de Saída
```
Case 1:

                                5 2 7

                                Case 2:

                                8 3 10 1 6 14 4 7 13
```