Step by level in binary tree

Question

Description of the problem I need to solve: "A level walk on a tree, first list the root, then all nodes that are at level 1 then all nodes of level 2, etc. Write a procedure to list the nodes of a binary tree by level."

Since it is necessary to go through a binary tree, I used recursiveness in the writing of the method, but I cannot get the expected result. Follow the method I wrote:

public void imprimeNivel(No no) {
    if(no != null) {

        if(no == raiz) {
            System.out.println(raiz.getConteudo());
        } 
            if(no.getFilhoDireita() == null && no.getFilhoEsquerda() == null) {

            } else if(no.getFilhoDireita() == null) {
                System.out.printf("%d ", no.getFilhoEsquerda().getConteudo());
            } else if(no.getFilhoEsquerda() == null) {
                System.out.printf("%d ", no.getFilhoDireita().getConteudo());
            } else {
                System.out.printf("%d ", no.getFilhoEsquerda().getConteudo());
                System.out.printf("%d ", no.getFilhoDireita().getConteudo());
            }

            System.out.println();
            imprimeNivel(no.getFilhoEsquerda());
            imprimeNivel(no.getFilhoDireita());

    }
}

Could someone give me an idea of how to solve this problem?

Answer 1

Code

The most straightforward and simple algorithm code I know to traverse the tree in levels is using a queue:

public void walkLevels(No no) {
    if (no == null) throw new IllegalArgumentException("Tree node cannot be null!");
    Deque<No> fila = new ArrayDeque<>();
    fila.add(no);
    while (!fila.isEmpty()) {
        No atual = fila.removeFirst();
        System.out.printf("%s, ", atual.getConteudo());
        if (atual.getFilhoEsquerda() != null) fila.add(atual.getFilhoEsquerda());
        if (atual.getFilhoDireita() != null) fila.add(atual.getFilhoDireita());
    }
}

Algorithm

The basic idea of the algorithm is:

1. Start with the root
2. Consume the first node of the queue
3. Add his children, if you have any, at the end of the queue
4. Repeat steps 2 and 3 until you clear the queue

Since child nodes are always added to the end of the queue, this ensures that all nodes of the previous level will be executed before the next level.

Table test

Using as an example tree of Wikipedia:

We can make a representation of the execution like this:

    Fila      Ação
0   -         Início, coloca o nó raiz na fila   
1   8         Consome 8,  adiciona filhos 3 e 10 ao final   
2   3 10      Consome 3,  adiciona filhos 1 e 6 ao final       
3   10 1 6    Consome 10, adiciona filho 14 da direita ao final        
4   1 6 14    Consome 1,  sem filhos então nada a fazer        
5   6 14      Consome 6,  adiciona filhos 4 e 7 ao final      
6   14 4 7    Consome 14, adiciona filho 13 da esquerda ao final        
7   4 7 13    Consome 4,  sem filhos então nada a fazer                    
8   7 13      Consome 7,  sem filhos então nada a fazer      
9   13        Consome 13, sem filhos então nada a fazer    
10  -         Fila vazia --> Terminou!     

Full code on my Github