by using java

this is bst class

/************************ BST.java **************************

* generic binary search tree

*/

import java.util.*;

public class BST> implements Iterable {

protected BSTNode root = null;

public BST() {

}

public BST(BSTNode p) {

root = p;

}

public void clear() {

root = null;

}

public boolean isEmpty() {

return root == null;

}

protected void visit(BSTNode p) {

System.out.print(p.key + " ");

}

public T search(T el) {

return search(el, root);

}

//recursive search

protected T search(T el, BSTNode p) {

if (p == null)

return null;

else if(el.compareTo(p.key )

return search(el, p.left);

else if(el.compareTo(p.key) > 0)

return search(el, p.right );

else

return p.key;

}

/*

//Iterative search

public T search(T el) {

BSTNode p = root;

while (p != null) {

if (el.equals(p.key))

return p.key;

else if (el.compareTo(p.key)

p = p.left;

else p = p.right;

}

return null;

}

*/

public boolean isInTree(T el) {

return search(el) != null;

}

public void breadthFirst() {

BSTNode p = root;

LLQueue> queue = new LLQueue>();

if (p != null) {

queue.enqueue(p);

while (!queue.isEmpty()) {

p = queue.dequeue();

visit(p);

if (p.left != null)

queue.enqueue(p.left);

if (p.right != null)

queue.enqueue(p.right);

}

}

}

public void preorder() {

preorder(root);

}

protected void preorder(BSTNode p) {

if (p != null) {

visit(p);

preorder(p.left);

preorder(p.right);

}

}

public void inorder() {

inorder(root);

}

protected void inorder(BSTNode p) {

if (p != null) {

inorder(p.left);

visit(p);

inorder(p.right);

}

}

public void postorder() {

postorder(root);

}

protected void postorder(BSTNode p) {

if (p != null) {

postorder(p.left);

postorder(p.right);

visit(p);

}

}

public void insert(T el) {

root = insert(el, root);

}

protected BSTNode insert(T el, BSTNode p) {

if( p == null )

p = new BSTNode(el);

else if(el.compareTo(p.key )

p.left = insert(el, p.left );

else if( el.compareTo(p.key ) > 0 )

p.right = insert(el, p.right );

return p;

}

/* iterative version

public void insert(T el) {

BSTNode p = root, prev = null;

while (p != null) { // find a place for inserting new node;

prev = p;

if (el.compareTo(p.key)

p = p.left;

else p = p.right;

}

if (root == null) // tree is empty;

root = new BSTNode(el);

else if (el.compareTo(prev.key)

prev.left = new BSTNode(el);

else prev.right = new BSTNode(el);

}

*/

public void delete (T el) {

root = delete (el, root);

}

//recursive delete by copying

protected BSTNode delete(T el, BSTNode p) {

if (p == null)

return null;

else if (el.compareTo(p.key)

p.left = delete(el, p.left); // delete from left

else if (el.compareTo(p.key) > 0) //target is greater than p.key

p.right = delete(el, p.right);

else { //p.key is the key to be deleted

if (p.left == null || p.right == null) {//if there is one or no child

if (p.left == null) //if no left child

p = p.right;

else //if no right child or no child at all

p = p.left;

}

else { //if p has two children

BSTNode tmp = getMinNode(p.right);//get the successor of the p.key

p.key = tmp.key; //replace p.key with its successor

p.right = delete(tmp.key, p.right); //delete the successor from the right subtree.

}

}

return p;

}

//given a non-empty tree, retuns the node with the minimum key.

private BSTNode getMinNode(BSTNode p) {

BSTNode tmp = p;

while (tmp.left != null)

tmp = tmp.left;

return tmp;

}

//Iterative delete by copying

/*

public void deleteByCopying(T el) {

BSTNode node, p = root, prev = null;

while (p != null && !p.key.equals(el)) { // find the node p

prev = p; // with element el;

if (el.compareTo(p.key)

p = p.left;

else p = p.right;

}

node = p;

if (p != null && p.key.equals(el)) {

if (node.right == null) // node has no right child;

node = node.left;

else if (node.left == null) // no left child for node;

node = node.right;

else {

BSTNode tmp = node.left; // node has both children;

BSTNode previous = node; // 1.

while (tmp.right != null) { // 2. find the rightmost

previous = tmp; // position in the

tmp = tmp.right; // left subtree of node;

}

node.key = tmp.key; // 3. overwrite the reference

// to the element being deleted;

if (previous == node) // if node's left child's

previous.left = tmp.left; // right subtree is null;

else previous.right = tmp.left; // 4.

}

if (p == root)

root = node;

else if (prev.left == p)

prev.left = node;

else prev.right = node;

}

else if (root != null)

System.out.println("el " + el + " is not in the tree");

else System.out.println("the tree is empty");

}

*/

public Iterator iterator() {

return new BSTIterator();

}

private class BSTIterator implements Iterator {

BSTNode p = root;

LLQueue> queue;

public BSTIterator() {

queue = new LLQueue>();

queue.enqueue(p);

}

public boolean hasNext() {

return !queue.isEmpty();

}

public T next() {

p = queue.dequeue();

if (p.left != null)

queue.enqueue(p.left);

if (p.right != null)

queue.enqueue(p.right);

return p.key;

}

public void remove() {

// not implemented

}

}

//Generic BSTNode class;

private class BSTNode> {

protected T key;

protected BSTNode left, right;

public BSTNode() {

left = right = null;

}

public BSTNode(T el) {

this(el,null,null);

}

public BSTNode(T el, BSTNode lt, BSTNode rt) {

key = el; left = lt; right = rt;

}

}

}

2 Write each of the following methods inside the BST class 11 Marks 1 eachl not element does A recursive method that returns the level of the node containing el or -1 i exist in the tree Exomple: Level of node 12 is 3 A recursive method that retuarns true if the tree referenced by p is balanced (n) protected boolean isBalanced (BSTodeT p) betweern Hint: A balanced tree is oither empty or one in which for each node,the difference bet the heights of left and right sub-trees is less than 2 and both lett and rightsub-es balanced (iv) public void printPath(T el, BST NodeTyp) A recursive method that prints all the nodes in the path from the root of the tree referenced by ? to the node containing el. Hint: For the tree shown in the folowing figure, the output should be: t0, 15, 12 Note: For each of the recursive methods above, you need to have a public overloaded version of the method (without parameter p) that calls the recursive version with root as the initial value of p It is this public method you will call in the TestintegerBST class. 1 2 20 2 Write each of the following methods inside the BST class 11 Marks 1 eachl not element does A recursive method that returns the level of the node containing el or -1 i exist in the tree Exomple: Level of node 12 is 3 A recursive method that retuarns true if the tree referenced by p is balanced (n) protected boolean isBalanced (BSTodeT p) betweern Hint: A balanced tree is oither empty or one in which for each node,the difference bet the heights of left and right sub-trees is less than 2 and both lett and rightsub-es balanced (iv) public void printPath(T el, BST NodeTyp) A recursive method that prints all the nodes in the path from the root of the tree referenced by ? to the node containing el. Hint: For the tree shown in the folowing figure, the output should be: t0, 15, 12 Note: For each of the recursive methods above, you need to have a public overloaded version of the method (without parameter p) that calls the recursive version with root as the initial value of p It is this public method you will call in the TestintegerBST class. 1 2 20