Delete nodes from BST Giving null pointer Exception

#1

import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);

    int t = scan.nextInt();
        for(int i=0;i<t;i++){
            int n = scan.nextInt();
            int arr1[] = new int[n];
            for(int j = 0;j<n;j++){
                arr1[j] = scan.nextInt();
            }
            int m = scan.nextInt();
            int arr2[] = new int[m];
            for(int j = 0;j<m;j++){
                arr2[j] = scan.nextInt();
            }
            BST tree = new BST(arr1,arr2);
            tree.display();
            
        }
    }
}

class BST{
private class Node{
int data;
Node left;
Node right;
}
private Node root;
public BST(int[] arr, int[] arr2){
// Arrays.sort(arr);
this.root= construct(arr,0,arr.length-1);
for(int i=0;i<arr2.length;i++){
remove(this.root,null,false,arr2[i]);
}
}

private Node construct(int[] arr, int lo,int hi){
    if(lo>hi){
        return null;
    }
    int mid = (lo+hi)/2;
    Node node = new Node();
    node.data = arr[mid];
    node.left = construct(arr,lo,mid-1);
    node.right = construct(arr,mid+1,hi);
    return node;
}
private void remove(Node node, Node parent, boolean ilc,int item){
    if(item<node.data){
        remove(node.left,node,true,item);
    }
    else if(item>node.data){
        remove(node.right,node,false,item);
    }
    else{
        if(node.right==null && node.left==null){
            if(ilc){
                parent.left = null;
            }else{
                parent.right = null;
            }
        }
        else if(node.right!=null&& node.left ==null){
            if(ilc){
                parent.left = node.right;
            }else{
                parent.right = node.right;
            }
        }
        else if(node.left!=null&&node.right==null){
            if(ilc){
                parent.left = node.left;
            }
            else{
                parent.right = node.left;
            }
        }
        else{
            int max = max(node.left);
            node.data = max;
            remove(node.left,node,true,max);
        }
    }
}
private int max(Node node){
    if(node.right == null){
        return node.data;
    }
    
    return max(node.right);
}
public void display(){
    display(this.root);
}
//preorder
public void display(Node node){
    if(node==null){
        return;
    }
    System.out.print(node.data+" ");
    display(node.left);
    display(node.right);
}

}
please check the code

#2

import java.util.*; public class Main { public static void main(String args[]) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); for(int i=0;i<t;i++){ int n = scan.nextInt(); int arr1[] = new int[n]; for(int j = 0;j<n;j++){ arr1[j] = scan.nextInt(); } int m = scan.nextInt(); int arr2[] = new int[m]; for(int j = 0;j<m;j++){ arr2[j] = scan.nextInt(); } BST tree = new BST(arr1,arr2); tree.display(); } } } class BST{ private class Node{ int data; Node left; Node right; } private Node root; public BST(int[] arr, int[] arr2){ Arrays.sort(arr); this.root= construct(arr,0,arr.length-1); for(int i=0;i<arr2.length;i++){ remove(this.root,null,false,arr2[i]); } } private Node construct(int[] arr, int lo,int hi){ if(lo>hi){ return null; } int mid = (lo+hi)/2; Node node = new Node(); node.data = arr[mid]; node.left = construct(arr,lo,mid-1); node.right = construct(arr,mid+1,hi); return node; } private void remove(Node node, Node parent, boolean ilc,int item){ if(item<node.data){ remove(node.left,node,true,item); } else if(item>node.data){ remove(node.right,node,false,item); } else{ if(node.right==null && node.left==null){ if(ilc){ parent.left = null; }else{ parent.right = null; } } else if(node.right!=null&& node.left ==null){ if(ilc){ parent.left = node.right; }else{ parent.right = node.right; } } else if(node.left!=null&&node.right==null){ if(ilc){ parent.left = node.left; } else{ parent.right = node.left; } } else{ int max = max(node.left); node.data = max; remove(node.left,node,true,max); } } } private int max(Node node){ if(node.right == null){ return node.data; } return max(node.right); } public void display(){ display(this.root); } //preorder public void display(Node node){ if(node==null){ return; } System.out.print(node.data+" "); display(node.left); display(node.right); } }

#3

Hi,
see when you are making the tree with the help of array first of all the child of a particular parent node at ith index i are 2i+1(left child) and 2i+2 (right child) and then in remove function don’t use the return type void but take it as node and when your node.data==item then in the case when both the children donot exist for that node then you return null else if left child don’t exist then return node.right and further think for all the cases.

#4

The tree construction you suggesting is for Level Order to Bst and input is not in level order

#5

Hi,see when you are constructing a bst you check every data which you have input and see that if that particular element is smaller than your node(in starting which is the root) then you will put that element in node.left else node.right and check like this until we get null and then we make a new node and put that node in its correct position.
The method you have done is also fine as you have first sorted the array.

#6

Hi @Vaibhav-Garg-1998823966894298
as you are not responding to the doubt I am marking your doubt as resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “Ask Doubt” section, when your doubt is resolved.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.