Method that returns the levels of a Binary Tree

Question

Method that returns the levels of a Binary Tree

Navigation

#1 by (1 votes)

2

I am trying to implement a Binary Tree for the first time but I am having difficulty in the method that returns the amount of levels present in the tree once it is populated.

The method below can perfectly navigate all the elements present in each level of the Tree, the problem is in the part of restricting when the method should keep 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;
}

java

asked by anonymous 10.09.2017 / 06:34

1 answer

Finding matlab command in python? Inverse transformation in R for continuous var whose max value = Inf

score 1 · Accepted Answer

Both height with the amount of elements are much easier recursively using a Depth First Search (DFS) algorithm, like this:

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 your example, these are more complex and / or extensive, although they have other properties, for example, to go from level to level instead of in depth.

Your code is doing the following:

Starts from 8 increases to level 1 and stacks 3 and 10.
Then parse the 3, increase the level to 2, and stack the 1 and the 6
Next goes to 10, and raises the level to 3 by stacking 13

At this point it is no longer right because 3 and 10 are still at 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 also stack the node level so that each node considers the level of the parent node to discover its own, and its always the one of the parent plus 1. To facilitate it one can create an auxiliary class that has a reference to Node and its nivel , modifying Queue to use that 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;
}