import java.util.Arrays;
public class BST {
private class Node{
int data;
Node left;
Node right;
}
private Node root;
public BST(int [] arr) {
this.root = construct(arr,0,arr.length-1);
}
private Node construct(int[] arr,int lo,int hi) {
if(lo>hi) {
return null;
}
// mid index
int mid = (lo+hi)/2;
// set the element at mid index as root node
Node nn = new Node();
nn.data = arr[mid];
nn.left = construct(arr,lo,mid-1);
nn.right = construct(arr,mid+1,hi);
return nn;
}
public void display() {
this.display(this.root);
}
private void display(Node node) {
if(node == null) {
return;
}
String str = "";
if(node.left == null) {
str += ".";
}else {
str += node.left.data;
}
str += "=>"+node.data+"<=";
if(node.right == null) {
str += ".";
}else {
str += node.right.data;
}
System.out.println(str);
display(node.left);
display(node.right);
}
public void preOrder() {
this.preOrder(this.root);
System.out.println(" END");
}
private void preOrder(Node node) {
if(node == null) {
return;
}
System.out.print(node.data+", ");
preOrder(node.left);
preOrder(node.right);
}
public void remove(int item) {
remove(this.root,null,false,item);
}
private void remove(Node node,Node parent,boolean isLeftChild,int item) {
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(isLeftChild) {
parent.left = null;
}else {
parent.right = null;
}
}
else if(node.left==null && node.right!=null) {
if(isLeftChild) {
parent.left = node.right;
}else {
parent.right = node.right;
}
}
else if(node.left!=null && node.right==null) {
if(isLeftChild) {
parent.left = node.left;
}else {
parent.right = node.left;
}
}
else {
int max = max(node.left);
node.data = max;
remove(node.left,node,true,max);
}
}
}
public int max() {
return max(this.root);
}
private int max(Node node) {
if(node.right == null) {
return node.data;
}
return max(node.right);
}
public static void main(String[] args) {
int[] arr = {5 ,3 ,2 ,4 ,7 ,6 ,8};
Arrays.sort(arr);
int[] in = arr;
BST tree = new BST(in);
int[] remove = {2,3,5};
for(int i=0;i<remove.length;i++) {
tree.remove(remove[i]);
}
tree.preOrder();
}
}
//sir for this code I’m getting 4 7 6 8 as my answer but the given output is 6 4 7 8