Error related to binary tree removal and child relocation (java.lang.Nullpointerexception)

Question

Hello, everyone. I started studying the Java language recently and decided to try to create a binary tree with three features:

1 - Add element to tree

2 - Search and print tree widget

3 - Remove tree element (relocating your children)

The third feature should be made so that, for example, a binary tree that has root value 3 and children 2 and 5, upon receiving the command to remove value 3, should keep values 2 and 5 in the tree. That is, when removing the parent knot, your children are not removed, but reinserted into the tree.

With that in mind, I created the Tree class that follows below:

package org.hello;

import javax.swing.JOptionPane;

public class Arvore {
    int valor;
    Arvore left = null;
    Arvore right  = null;
    String e,d;
    int size;

    Arvore(){
        size=0;
    }
    Arvore(int x){
        valor=x;
        size=0;
    }

    int insert(Arvore root,int valor){
        Arvore a = new Arvore(valor);
        if(root == null){
            root = a;
            root.size++;
            JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
        }
        else{
            if(valor > root.valor){
                if(root.right == null){
                    root.right = a;
                    root.size++;
                    a.size = root.size;
                    JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
                }
                else{
                    return insert(root.right,valor);
                }
            }
            else {
                if(valor < root.valor){
                    if(root.left == null){
                        root.left = a;
                        root.size++;
                        a.size = root.size;
                        JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
                    }
                    else{
                        return insert(root.left,valor);
                    }
                }
                else{
                    if(valor == root.valor){
                        JOptionPane.showMessageDialog(null, "Elemento já existente.");
                    }
                }
            }


        }
        return 0;
    }

    int buscar(Arvore root, int valor){
        if(root == null){
            JOptionPane.showMessageDialog(null, "Elemento não encontrado.");
        }
        else{
            if(root.valor == valor){ 
                if(root.left == null ){
                    root.e = "vazio" ;
                }
                else{
                    root.e = Integer.toString(root.left.valor);
                }
                if(root.right == null){
                    root.d = "vazio";
                }
                else{
                    root.d = Integer.toString(root.right.valor);
                }
                JOptionPane.showMessageDialog(null,"Valor: "+root.valor+"\n"+"Esquerdo: "+root.e+"\n"+"Direito: "+root.d+"\n\n");
            }
            else{
                if(root.valor < valor){
                    return buscar(root.right,valor);
                }
                else{
                    return buscar(root.left,valor);
                }
            }
        }
        return 0;
    }
Arvore novo_no(Arvore source,Arvore dest){
    if(source.right==null && source.left==null){
        return dest;
    }
    else{
        if(source.right != null && source.left != null){
        dest.insert(dest,source.left.valor);
        dest.insert(dest,source.right.valor);
        dest = novo_no(source.left,dest);
        dest = novo_no(source.right,dest);
        return dest;
        }
        else{
            if(source.right != null && source.left == null){
                dest.insert(dest,source.right.valor);
                dest = novo_no(source.right,dest);
                return dest;
            }
            else{
                dest.insert(dest,source.left.valor);
                dest = novo_no(source.left,dest);
                return dest;
            }
        }
    }
}
int remove(Arvore root, int valor){
    if(root==null){
        JOptionPane.showMessageDialog(null,"Elemento não cadastrado.");
    }
    else{
        if(root.valor == valor){
            Arvore dest = new Arvore();
            dest = null;
            root = novo_no(root,dest);
            return 0;
        }
        else{
            if(root.valor > valor){
                return remove(root.left,valor);
            }
            else{
                return remove(root.right,valor);
            }
        }
    }
    return 0;
}
} 

The functions 'Insert' and 'fetch', responsible for inserting and fetching the elements in the tree, respectively, are working normally. Already the 'remove' and 'new_no' functions, which act together to remove an element from the tree, do not work well, generating the error mentioned in the title.

OBS: I’m not sure if the two functions have errors or if only one of them is wrong. So I’d like your help to understand why the program doesn’t work the way you want it to.

On the behaviour of the programme:

By adding the numbers 5,6 and 4 to the tree as a test, and searching for any of them, the program works perfectly. However, when trying to remove any of the child nodes(4 and 6), the program acts as if it has removed them, when it is actually still possible to pick them up from the tree. When attempting to remove the parent node(5), the program terminates and displays the error lines below:

Exception in thread "main" java.lang.NullPointerException
at org.hello.Arvore.novo_no(Arvore.java:100)
at org.hello.Arvore.remove(Arvore.java:128)
at org.hello.Principal.main(Principal.java:40)
at org.hello.Principal.main(Principal.java:36)
at org.hello.Principal.main(Principal.java:41)
at org.hello.Principal.main(Principal.java:36)
at org.hello.Principal.main(Principal.java:26)
at org.hello.Principal.main(Principal.java:26)
at org.hello.Principal.main(Principal.java:22)

I checked the lines mentioned above, but could not understand what was wrong. So I count on your help to understand what happened. Below is the main function:

package org.hello;
import java.util.Scanner;

import javax.swing.JOptionPane;

public class Principal {

static Arvore pai = null;

public static void main(String[] args){

    int escolha = Integer.parseInt(JOptionPane.showInputDialog("Escolha uma opção: \n\n 1-Adicionar elemento \n 2-Buscar elemento \n 3-Remover elemento \n"));

    switch(escolha){
    case 1:
        int valor = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser adicionado: "));
        if(pai==null){
            Arvore a = new Arvore(valor);
            pai = a;
            JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
            pai.size++;
            main(null);
            break;
        }
        pai.insert(pai, valor);
        main(null);
        break;
    case 2:
        int valor2 = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser buscado: "));
        if(pai == null){
            JOptionPane.showMessageDialog(null,"Elemento não existente.");
            main(null);
            break;
        }
        pai.buscar(pai, valor2);
        main(null);
        break;
    case 3:
        int valor3 = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser removido: "));
        pai.remove(pai, valor3);
        main(null);
        break;
    }
}
}

Thank you in advance!

Hello again. According to @cleberz, the following block was not working by providing a null value for the function novo_no:

 ...    
if(root.valor == valor){
    Arvore dest = new Arvore();
    dest = null; //pra quê anular se você 
                 //acabou de inicializar?
    root = novo_no(root,dest); //isso manda um nulo aqui
    return 0;
}
... 

After the correction, this block was like this:

...    
if(root.valor == valor){
    Arvore dest = new Arvore();
    root = novo_no(root,dest);
    /* 1 */
return 0;
}
...

However, on the line /* 1 */, if I put 3 JOptionPane.showMessageDialog() to show the value of the new node(root) and the value of your 2 children, I have the following return:

node value: 0

value right node: 4

value left node: null

That’s when we just add the numbers 5, 4 and 6 to the tree. But although this is not the desired return, since the value of the node should be the number 4, while the number 6 would be his right child, when fetching the value 5 in the tree again he is still there, even if the value of root should have been changed before the function remove return. I wonder why the root value does not change, in this case.

Answer 1

The problem specifically of Nullpointerexception on that line is occurring because its method remove() is passing a null value in the parameter dest function new in the() :

    ...    
    if(root.valor == valor){
        Arvore dest = new Arvore();
        dest = null; //pra quê anular se você 
                     //acabou de inicializar?
        root = novo_no(root,dest); //isso manda um nulo aqui
        return 0;
    }
    ...

The function new in the() in turn is trying to access a member (in this case a method) of that parameter without checking if it is null:

Arvore novo_no(Arvore source,Arvore dest){
  if(source.right==null && source.left==null){
      return dest;
  }
  else{
      if(source.right != null && source.left != null){
      dest.insert(dest,source.left.valor); //dest é nulo aqui

Well, that’s the NPE problem with your code. But I see some other problems (typical of beginners, of course) like:

1 - using the same class for the Tree instead of using one class for the Tree, and another for the node. The Tree class can contain the pointer to the root and the number of nodes, and the node class can contain only the value of its node, and pointers to its child nodes. 2 - no need to store the String version of the values for later display (variables d and and). This can be done in the method that prints.

Answer 2

I managed to make the program work. Basically, I didn’t understand why a function like insert could alter the root, while remove did not do the same. It turns out that, apparently, a variable does not change itself within the function. In order for this to happen, the changed value within the function must be returned and stored in a new variable, and the old variable must be matched to this new variable, so that its value changes. However, when it comes to a variable within a variable, as is the case of class objects Arvore in my program, it is not necessary to return this value since, for example, the object root acts as a "pointer", which points to its attributes, and can modify root.left, for example. This similarity to pointers explains why root does not change itself, since it would take a pointer pointer to do so.

Therefore, I have made the following modifications:

1 - In function novo_no of class Arvore :

...
if(source.right==null && source.left==null){
        dest = null;
/*retorna um valor nulo para o nó, impedindo que o programa funcione 
de forma errada, já que, por ter sido inicializado dessa forma: 
'Arvore dest = new Arvore(); 
dest retornaria como um objeto Arvore de valor 0 */

        return dest;
    }
...

2 - In function remove of class Arvore :

... 
root.left = remove(root.left,valor);
...

...
root.right = remove(root.right,valor);
...

/* Dessa forma eu altero os nós esquerdos e direitos, já que eles não 
precisam ser retornados para a função main para serem modificados, como eu
havia dito anteriormente*/

3 - In function main of the Main class:

...
case 3:
        int valor3 = Integer.parseInt(JOptionPane.showInputDialog("Digite o
  valor a ser removido: "));
        Arvore c = pai.remove(pai, valor3);
        pai = c;
        main(null);
        break;
    /* Aqui, a variável c recebe o valor de retorno da função remove. Se 
essa função modificasse apenas os nós filhos, essa variável seria desnecessária. Mas como a 
raiz também pode ser removida, então é necessário retornar esse valor da função e igualá-lo 
ao pai.*/

...

But why the function insert worked normally if it does not return any Tree object and yet it changes the value of pai ? That’s simple:

...
case 1:
        int valor = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser adicionado: "));
        if(pai==null){
            Arvore a = new Arvore(valor);
            pai = a;
            JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
            pai.size++;
            main(null);
            break;
        }
        pai.insert(pai, valor);
        main(null);
        break;

/*Como é possível notar, o case 1 da função main tinha uma condição que
 tinha a função de alterar o 'pai' caso esse fosse nulo. Por isso, a função 'insert' era 
usada apenas para adicionar outros nós, não precisando alterar o valor da raiz. Por isso 
 não foi necessário armazenar o retorno dessa função, já que ela não era usada para modificar a raiz.*/

I think that’s all. I appreciate the answers and hope that my question can help other people.