Binary Search Tree in Java

BST.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

class IntBSTNode {
	protected int key;
	protected IntBSTNode left, right;

	public IntBSTNode() {
		left = right = null;
	}

	public IntBSTNode(int el) {
		this(el, null, null);
	}

	public IntBSTNode(int el, IntBSTNode lt, IntBSTNode rt) {
		key = el;
		left = lt;
		right = rt;
	}
}

class IntBST {
	protected IntBSTNode root;

	public IntBST() {
		root = null;
	}

	protected void visit(IntBSTNode p) {
		System.out.print(p.key + " ");
	}

	public IntBSTNode search(int el) {
		return search(root, el);
	}

	public IntBSTNode search(IntBSTNode p, int el) {
		while (p != null) {
			if (el == p.key)
				return p;
			else if (el < p.key)
				p = p.left;
			else
				p = p.right;
		}
		return null;
	}

	public void breadthFirst() {
		IntBSTNode p = root;
		ArrayDeque<Object> q = new ArrayDeque<Object>();
		if (p != null) {
			q.add(p);
			while (!q.isEmpty()) {
				p = (IntBSTNode) q.remove();
				visit(p);
				if (p.left != null)
					q.add(p.left);
				if (p.right != null)
					q.add(p.right);
			}
		}
	}

	public void preorder() {
		preorder(root);
	}

	protected void preorder(IntBSTNode p) {
		if (p != null) {
			visit(p);
			preorder(p.left);
			preorder(p.right);
		}
	}

	public void inorder() {
		inorder(root);
	}

	protected void inorder(IntBSTNode p) {
		if (p != null) {
			inorder(p.left);
			visit(p);
			inorder(p.right);
		}
	}

	public void postorder() {
		postorder(root);
	}

	protected void postorder(IntBSTNode p) {
		if (p != null) {
			postorder(p.left);
			postorder(p.right);
			visit(p);
		}
	}

	public void insert(int el) {
		IntBSTNode p = root, prev = null;
		while (p != null) {
			prev = p;
			if (p.key < el)
				p = p.right;
			else
				p = p.left;
		}
		if (root == null)
			root = new IntBSTNode(el);
		else if (prev.key < el)
			prev.right = new IntBSTNode(el);
		else
			prev.left = new IntBSTNode(el);
	}

	public void deleteByMerging(int el) {
		IntBSTNode tmp, node, p = root, prev = null;
		while (p != null && p.key != el) {
			prev = p;
			if (p.key < el)
				p = p.right;
			else
				p = p.left;
		}
		node = p;
		if (p != null && p.key == el) {
			if (node.right == null)
				node = node.left;
			else if (node.left == null)
				node = node.right;
			else {
				tmp = node.left;
				while (tmp.right != null)
					tmp = tmp.right;
				tmp.right = node.right;
				node = node.left;
			}
			if (p == root)
				root = node;
			else if (prev.left == p)
				prev.left = node;
			else
				prev.right = node;
		} else if (root != null)
			System.out.println("key " + el + " is not in the tree");
		else
			System.out.println("the tree is empty");
	}
}

public class BST {
	public static void main(String args[]) throws IOException {
		IntBST tree = new IntBST();

		int choice;
		int el;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		do {
			System.out.println("Enter your choice:");
			System.out
					.println("1.INSERT \t2.DELETE \t3.TRAVERSE \t4.SEARCH \t5.EXIT");
			choice = Integer.parseInt(br.readLine());
			switch (choice) {
			case 1:
				System.out.println("\t\tEnter a number:");
				System.out.print("\t\t");
				el = Integer.parseInt(br.readLine());
				tree.insert(el);
				break;
			case 2:
				System.out.println("\t\tEnter a number:");
				System.out.print("\t\t");
				el = Integer.parseInt(br.readLine());
				tree.deleteByMerging(el);
				break;
			case 3:
				System.out.println("\t\tEnter your choice:");
				System.out
						.println("\t\t1.BREADTH FIRST TRAVERSAL \t2.DEPTH FIRST TRAVERSAL");
				System.out.print("\t\t");
				choice = Integer.parseInt(br.readLine());
				switch (choice) {
				case 1:
					tree.breadthFirst();
					break;
				case 2:
					System.out.println("\t\tEnter your choice:");
					System.out
							.println("\t\t1.PREORDER\t 2.INORDER\t 3.POSTORDER");
					System.out.print("\t\t");
					choice = Integer.parseInt(br.readLine());
					switch (choice) {
					case 1:
						tree.preorder();
						break;
					case 2:
						tree.inorder();
						break;
					case 3:
						tree.postorder();
						break;
					default:
						System.out
								.println("\t\tInvalid argument,return to main menu");
						break;
					}
					break;
				default:
					System.out
							.println("\t\tInvalid argument,return to main menu");
					break;
				}
				break;
			case 4:
				System.out.println("\t\tEnter a number:");
				System.out.print("\t\t");
				el = Integer.parseInt(br.readLine());
				if (tree.search(el) != null)
					System.out.println("\t\tElement is present");
				else
					System.out.println("\t\tElement is not present");

				break;
			case 5:
				break;
			}
		} while (choice != 5);
	}
}