public class BinaryTreeSearch {

public Node root = null;

public class Node {

public int data;

public Node parent;

public Node left;

public Node right;

public Node(int input) {

this.data = input;

this.parent = null;

this.left = null;

this.right = null;

}// Node.constructor

}// class Node

public void insert(int input) {

Node newNode = new Node(input);

if (root == null)

root = newNode;

else {

Node x = root;

while (x != null) {

if (newNode.data > x.data) {

if (x.right == null) {

x.right = newNode;

newNode.parent = x;

return;

}

x = x.right;

} else {

if (x.left == null) {

x.left = newNode;

newNode.parent = x;

return;

}

x = x.left;

}

} // while

}

}// BinaryTreeSearch.insert

public void delete(int input) {

Node z = search(input);

if (z.left == null && z.right == null) {

if (z.parent.data > z.data)

z.parent.left = null;

else

z.parent.right = null;

} // in case z has any children nodes

else if (z.left == null) {

if (z.parent.left == z)

z.parent.left = z.right;

else

z.parent.right = z.right;

} else if (z.right == null) {

if (z.parent.left == z)

z.parent.left = z.left;

else

z.parent.right = z.left;

} // in case z has one children node

else {

int toBeReplaced = maximum(z.left).data;

delete(maximum(z.left).data);

z.data = toBeReplaced;

} // in case z has two children nodes

}// BinaryTreeSearch.delete

public Node search(int input) {

Node x = root;

boolean find = false;

while (x != null) {

if (x.data < input) {

x = x.right;

} else if (x.data == input) {

find = true;

break;

} else {

x = x.left;

}

}

if (find)

return x;

else

return null;

}// BinaryTreeSearch.seacrh

public Node minimum(Node z) {

Node x = z;

while (x.left != null) {

x = x.left;

}

return x;

}// BinaryTreeSearch.minimum

public Node maximum(Node z) {

Node x = z;

while (x.right != null) {

x = x.right;

}

return x;

}// BinaryTreeSearch.maximum

public Node predecessor(Node z) {

if (z.left != null)

return maximum(z.left);

Node thisNode = z;

Node x = z.parent;

while (x != null && z == x.left) {

z = x;

x = x.parent;

if (x == null)

return thisNode;

}

return x;

}// BinaryTreeSearch.predecessor

public Node successor(Node z) {

if (z.right != null)

return minimum(z.right);

Node thisNode = z;

Node x = z.parent;

while (x != null && z == x.right) {

z = x;

x = x.parent;

if (x == null)

return thisNode;

}

return x;

}// BinaryTreeSearch.successor

public void inorder_walk(Node root) {

if (root != null) {

inorder_walk(root.left);

System.out.print(root.data + " ");

inorder_walk(root.right);

}

}// BinaryTreeSearch.inorder_walk

public void preorder_walk(Node root) {

if (root != null) {

System.out.print(root.data + " ");

inorder_walk(root.left);

inorder_walk(root.right);

}

}// BinaryTreeSearch.preorder_walk

public void postorder_walk(Node root) {

if (root != null) {

inorder_walk(root.left);

inorder_walk(root.right);

System.out.print(root.data + " ");

}

}// BinaryTreeSearch.postorder_walk

public int getData(Node z) {

return z.data;

}// BinaryTreeSearch.getData

}// class BinaryTreeSearch

public static void main(String[] args) {

BinarySearchTree bst = new BinarySearchTree();

System.out.println("** BINARY TREE SEARCH **" + System.lineSeparator());

char cont;

do {

  System.out.println("1. insert ");

System.out.println("2. delete ");

System.out.println("3. search ");

System.out.println("4. maximum value ");

System.out.println("5. minimum value ");

Scanner scanner = new Scanner(System.in);

int selection = scanner.nextInt();

switch (selection) {

case 1:

System.out.println("enter input number : ");

bst.insert(scanner.nextInt());

break;

case 2:

System.out.println("enter integer value you want to delete : ");

bst.delete(scanner.nextInt());

break;

case 3:

System.out.println("enter integer value you want to find : ");

if (bst.search(scanner.nextInt()) != null)

System.out.println("search result = TRUE");

else

System.out.println("search result = FALSE");

break;

case 4:

System.out.println("Maximum value = "+ bst.getData(bst.maximum(bst.root)));

break;

case 5:

System.out.println("Minimum value = "+ bst.getData(bst.minimum(bst.root)));

break;

}

System.out.printf("inorder walk : ");

bst.inorder_walk(bst.root);

System.out.println();

System.out.printf("preorder walk : ");

bst.preorder_walk(bst.root);

System.out.println();

System.out.printf("postorder walk : ");

bst.postorder_walk(bst.root);

System.out.println();

System.out.println("\n[ continue ? type 'y' or 'n' ]");

cont = scanner.next().charAt(0);

} while (cont == 'y' || cont == 'Y');

}