my code give correct output on sample test case but after submitting all test cases fail
code link:https://ide.codingblocks.com/s/176255
All test case faik
i am not able to find whts wrong in my code
its been more than 24 hr no response???
@Rohan_singla
your remove function is not working for the cases when you want to remove the root node in such a case your parent will be null and you try to access parent.left or parent.right then it will show null pointer exception.
run your code for this test case
1
18
172 468 963 94 951 803 683 630 198 672 327 216 451 738 798 251 558 159
11
683 159 327 94 451 738 798 172 468 963 738
@kashishsingh8700 sir i have made the required changes for remove function…
please check it out
code link: https://ide.codingblocks.com/s/176255
@Rohan_singla
look sorting will change the shape of the tree.
the first node you add to tree should always be the root node
like for this testcase
1
18
172 468 963 94 951 803 683 630 198 672 327 216 451 738 798 251 558 159
11
683 159 327 94 451 738 798 172 468 963 738
172 has to be the root node
@Rohan_singla
it will be better if you make return type of the your remove function as Node not as void.
@kashishsingh8700 sir i have changed the input function of my code.
now please check whts wrong
code link:https://ide.codingblocks.com/s/178105
this code pass only 1 test case
@Rohan_singla
i have made few changes in your code tell me if you have any doubt.
import java.util.Scanner;
public class deletefrombst {
static Scanner scn = new Scanner(System.in);
public static void main(String[] args) {
deletefrombst b = new deletefrombst();
int n = scn.nextInt();// no of test cases
for (int i = 0; i < n; i++) {
int l = scn.nextInt();// length of array
int[] arr = takeinput(l);
// sortarray(arr);
BST bst = b.new BST(arr);
int rem = scn.nextInt();// no. of eleemnts to be removed
int[] remove = takeinput(rem);
// remove all elements in remove from bst
for (int j = 0; j < remove.length; j++) {
bst.remove(remove[j]);
}
bst.preorder();
}
}
public static int[] takeinput(int n) {
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
// System.out.println("enter the value of" + i + "index");
arr[i] = scn.nextInt();
}
return arr;
}
private class BST {
private class Node {
int data;
Node left;// every node can go to two places one right and one left so we have to store
// two
Node right;// addresses
Node(int value){
this.data=value;
}
}
private Node root;// through this node we can go to any node as like in linked list header node
// so we make this root node
// construct bst
public BST(int[] arr) {// constructor
this.root = arraytobinary(arr, this.root);
}
private Node arraytobinary(int[] arr, Node node) {
for (int j = 0; j < arr.length; j++) {
node = insert(node, arr[j]);
}
return node;
}
private Node insert(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value > node.data)
node.right = insert(node.right, value);
else if (value < node.data)
node.left = insert(node.left, value);
return node;
}
public int min(Node node) {
if (node.left == null) {
return node.data;
}
return min(node.left);
}
public int max() {
return max(this.root);
}
public int max(Node node) {
if (node.right == null) {
return node.data;
}
return max(node.right);// jo recursive call ka ans hoga whi hmara ans hoga to return lgake ye
// kia
}
public void remove(int item) {
if (item == this.root.data && root.left == null && root.right != null) {
int min = min(root.right);
root.data = min; // l.max<node<r.min
remove(root.right, root, false, min);
} else if (item == this.root.data && root.right == null && root.left != null) {
Node temp=this.root.left;
this.root.left=null;
this.root=temp;// you have to remove inorder successor :kashish
} else if (item == this.root.data && root.left == null && root.right == null) {
this.root = null;
}
else{
this.remove(this.root, null, false, item);
}// null bcoz here patrent is null
}
// false:if right child of parent
// true:if left child of parent ilc=is left child
private void remove(Node node, Node parent, boolean ilc, int item) {
// if node to be removed is not present in BST
if (node == null) {
return;
}
if (item > node.data) {
remove(node.right, node, false, item);
} else if (item < node.data) {
remove(node.left, node, true, item);
} else {
if (node.left == null && node.right == null) {
if (ilc) {
parent.left = null;
} else {
parent.right = null;
}
} else if (node.left == null && node.right != 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 min = min(node.right);
node.data = min; // l.max<node<r.min
remove(node.right, node, false, min);//you have to pass ilc=false here since you are moving right :kashish
}
}
}
public void preorder() {
this.preorder(this.root);
// System.out.println("END");
}
private void preorder(Node node) {
if (node == null) {
// System.out.println("null");
return;
}
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
}
this test case is passing my code
@Rohan_singla
check for this one
1
18
172 468 963 94 951 803 683 630 198 672 327 216 451 738 798 251 558 159
11
683 159 327 94 451 738 798 172 468 963 738
output
558 198 216 251 951 803 630 672
@Rohan_singla
hello buddy this is your final working code.
import java.util.Scanner;
public class deletefrombst {
static Scanner scn = new Scanner(System.in);
public static void main(String[] args) {
deletefrombst b = new deletefrombst();
int n = scn.nextInt();// no of test cases
for (int i = 0; i < n; i++) {
int l = scn.nextInt();// length of array
int[] arr = takeinput(l);
// sortarray(arr);
BST bst = b.new BST(arr);
int rem = scn.nextInt();// no. of eleemnts to be removed
int[] remove = takeinput(rem);
// remove all elements in remove from bst
for (int j = 0; j < remove.length; j++) {
bst.remove(remove[j]);
}
bst.preorder();
System.out.println();
}
}
public static int[] takeinput(int n) {
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
// System.out.println("enter the value of" + i + "index");
arr[i] = scn.nextInt();
}
return arr;
}
private class BST {
private class Node {
int data;
Node left;// every node can go to two places one right and one left so we have to store
// two
Node right;// addresses
Node(int value){
this.data=value;
}
}
private Node root;// through this node we can go to any node as like in linked list header node
// so we make this root node
// construct bst
public BST(int[] arr) {// constructor
this.root = arraytobinary(arr, this.root);
}
private Node arraytobinary(int[] arr, Node node) {
for (int j = 0; j < arr.length; j++) {
node = insert(node, arr[j]);
}
return node;
}
private Node insert(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value > node.data)
node.right = insert(node.right, value);
else if (value < node.data)
node.left = insert(node.left, value);
return node;
}
public int min(Node node) {
if (node.left == null) {
return node.data;
}
return min(node.left);
}
public int max() {
return max(this.root);
}
public int max(Node node) {
if (node.right == null) {
return node.data;
}
return max(node.right);// jo recursive call ka ans hoga whi hmara ans hoga to return lgake ye
// kia
}
public void remove(int item) {
if (item == this.root.data && this.root.left != null && this.root.right != null) {
int min = min(root.right);
root.data = min; // l.max<node<r.min
remove(root.right, root, false, min);
}
else if (item == this.root.data && this.root.left == null && this.root.right != null) {
Node temp=this.root.right;
this.root.right=null;
this.root=temp;
}
else if (item == this.root.data && this.root.right == null && this.root.left != null) {
Node temp=this.root.left;
this.root.left=null;
this.root=temp;// you have to remove inorder successor :kashish
} else if (item == this.root.data && this.root.left == null && this.root.right == null) {
this.root = null;
}
else{
this.remove(this.root, null, false, item);
}// null bcoz here patrent is null
}
// false:if right child of parent
// true:if left child of parent ilc=is left child
private void remove(Node node, Node parent, boolean ilc, int item) {
// if node to be removed is not present in BST
if (node == null) {
return;
}
if (item > node.data) {
remove(node.right, node, false, item);
} else if (item < node.data) {
remove(node.left, node, true, item);
} else {
if (node.left == null && node.right == null) {
if (ilc) {
parent.left = null;
} else {
parent.right = null;
}
} else if (node.left == null && node.right != 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 min = min(node.right);
node.data = min; // l.max<node<r.min
remove(node.right, node, false, min);//you have to pass ilc=false here since you are moving right :kashish
}
}
}
public void preorder() {
this.preorder(this.root);
// System.out.println("END");
}
private void preorder(Node node) {
if (node == null) {
// System.out.println("null");
return;
}
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
}
if you have any doubt regarding this ask me.
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.