Method that returns how many levels has a Binary Tree

Question

I’m trying to implement a Binary Tree for the first time but I’m having difficulty in the method that returns the amount of levels present in the tree after filled.

The method below can perfectly traverse all the elements present in each level of the Tree, the problem is in the part of restricting when the method must store a certain level with the variable "level+;". This way it returns the amount of elements inserted in the Tree.

I was able to implement the following code:

public int nivel(Node node){
    Node aux = raiz;
    int nivel = 0;
    if (aux == null) throw new IllegalArgumentException("Arvore vazia.");
    Deque<Node> fila = new ArrayDeque<>();
    fila.add(node);

    while (!fila.isEmpty()) {
        Node atual = fila.removeFirst();
        if (atual.getNodeEsquerda() != null)     fila.add(atual.getNodeEsquerda());
        if (atual.getNodeDireita() != null) fila.add(atual.getNodeDireita());
        nivel++;
    }
    return nivel;
}

Answer 1

So much height with the amount of elements are much easier doing recursively using an algorithm Depth First Search (DFS), thus:

public int nivel(Node no){
    if (no == null) return 0;

    return (int)Math.max(nivel(no.getNodeEsquerda())+1, nivel(no.getNodeDireita())+1);
}

Using Breadth First Search (BFS), which is his example, these become more complex and/or extensive, although they have other properties, such as, for example, travel level rather than depth.

Your code is doing the following:

• Start from 8 increases to level 1 and stack 3 and 10.
• Then analyze 3, raise the level to 2 and stack 1 and 6
• Next goes to the 10, and increases the level to 3 by stacking the 13

Right now it’s not right 3 and the 10 are still part of the same level. So the code will increase for each node giving the amount of nodes instead of the height.

One solution I see is to stack also the level of the node so that each node considers the level of the parent node to discover its, its always the one of the parent plus 1. To facilitate it can create an auxiliary class that has a reference to a Node and its nivel, modifying the Queue to use this type

Example:

private class NodeNivel { //classe para ter No e Nivel
    public Node no;
    public int nivel;

    public NodeNivel(Node no, int nivel){
        this.no = no;
        this.nivel = nivel;
    }
}

public int nivel(){
    Node aux = raiz;
    int nivel = 0;
    if (aux == null) throw new IllegalArgumentException("Arvore vazia.");
    Deque<NodeNivel> fila = new ArrayDeque<>(); //Agora Deque<NodeNivel>

    //cada vez que empilha leva nivel tambem,que é 1 para a raiz
    fila.add(new NodeNivel(aux, 1)); 

    while (!fila.isEmpty()) {
        NodeNivel atual = fila.removeFirst(); //Agora NodeNivel

        //estes ifs agora empilham NodeNivel aumentando o nivel em 1
        if (atual.no.getNodeEsquerda() != null) 
            fila.add(new NodeNivel(atual.no.getNodeEsquerda(), atual.nivel+1));
        if (atual.no.getNodeDireita() != null) 
            fila.add(new NodeNivel(atual.no.getNodeDireita(), atual.nivel+1));

        //verifica e atualiza o nivel maximo
        if (atual.nivel > nivel) 
            nivel = atual.nivel;
    }

    return nivel;
}