/************************ 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;

}

}

}

205- Data Structures S 205- Data ent WIIN Assignment # Submit by :Wednesday, 11104/2018 (in Class after class ID Instructions: . To submit this assignment using Blackboard Name 1. Answer exercises #5, #9 and #1 6 from pages 213-214 of the Text Book. [1 Mark each]. 2. 1 Marks: 1 each Write each of the following methods inside the BST class (i) protected int Level(T el, BSTNodeT ersive method that returns the level of the node cotaining el or-1 if element does not exist in the tree Example: Level of node 12 is 3 A recursive method that returns true if the tree refe Hint: A balanced tree is eith balanced (i) protected boolean isBalanced (BSTNodeT renced by p is balanced er empty or one in which for each node, the difference between the heights of left and right sub-trees is less than 2 and both left and right su (iv) public void printPath(T el, BSTNode T A recursive method that prints all the nodes in the path from the root of the tree referenced by p to the node containing el Hint: For the tree shown in the followi ure, the output should be: 10, 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 TestlntegerBST class 1 2 20