Answer Happy

You are given a binary search tree below and a Main class that
make use of the binary search tree. For this assignment, you will
complete the tree by completing the following methods:
Here's the given code:
import java.util.*;
public class Main {

public static void main(String[] args) {
BST<Integer> bst = new BST<>();

//add random integers to the tree
Random r = new Random();
for(int i=0; i<20; i++){
bst.add(r.nextInt(100)); //a binary search tree
//if the data is added in a sorted manner, the result is a
list.
//search would be O(n) instead of O(log n)
//bst.add(i); //creates a list like tree instead
//bst.add(10-i); //creates a list like tree instead
}
System.out.println("==Tree after added random integers.");
//System.out.println(bst);
bst.printTree();
System.out.println("Different traversal");
print("inorder :", bst.inorderIterator());
print("preorder :", bst.preorderIterator());
print("postorder :", bst.postorderIterator());
print("levelorder:", bst.levelorderIterator());

//randomly delete nodes from the tree
List<Integer> list = bst.inorder();
while(!list.isEmpty()){
int index = r.nextInt(list.size());
bst.remove(list.get(index));
System.out.println("=== removing " + list.get(index) + "
===");
//System.out.println(bst);
bst.printTree();
list.remove(index);
}
}
private static void print(String msg, Iterator it){
System.out.print(msg);
if (it.hasNext()) System.out.print(it.next());
while(it.hasNext()) System.out.print("," + it.next());
System.out.println();
}
}
/*
Complete the following methods:
height()
size()
clear()
inorder()
postorder()
*/
class BST<T extends Comparable<T>> {
private class Node {
T data;
Node left, right;
Node(T data) { this.data = data; }
}

private Node root;
//return the height of the tree
public int height() {
throw new UnsupportedOperationException("Todo");
}
//return the number nodes in the tree
public int size(){
throw new UnsupportedOperationException("Todo");
}

//clear the tree
public void clear(){
throw new UnsupportedOperationException("Todo");
}

public T find(T data) { return find(root, data);}
private T find(Node root, T data){
if (root == null) return null;
int result = data.compareTo(root.data);
if (result < 0) return root.left.data; //search left
subtree
if (result > 0) return root.right.data; //search right
subtree
return root.data; //found
}

public void add(T data) { root = add(root, data);}

private Node add(Node root, T data) {
if (root == null) return new Node(data); //add node and return new
subtree.
int result = data.compareTo(root.data);
if (result < 0) root.left = add(root.left, data); //add to left
sutree
else if (result > 0) root.right = add(root.right, data); //add
to right subtree
return root; //return updated subtree
}

private Node max(Node root){return
root.right==null?root:max(root.right);}

public void remove(T data){ root = remove(root, data); }

private Node remove(Node root, T data){

if (root == null) return null;

int result = data.compareTo(root.data);

if (result < 0) root.left = remove(root.left, data);
else if (result > 0) root.right = remove(root.right,
data);
else {

//case 1: node has two children,
if (root.left!=null && root.right !=null) {
Node leftMax = max(root.left);
root.left = remove(root.left, leftMax.data);
root.data = leftMax.data;

//case 2: node has no children, remove it.
} else if (root.left==null && root.right == null)
root = null;

//case 3: node has one child, replace node with child node
else
root = root.left == null ? root.right : root.left;
}

return root; //return the modify tree
}

public Iterator<T> preorderIterator() { return
preorder().iterator();}
public Iterator<T> inorderIterator() { return
inorder().iterator();}
public Iterator<T> postorderIterator() { return
postorder().iterator();}
public Iterator<T> levelorderIterator(){ return
levelorder().iterator();}

public List<T> preorder() {
List<T> list = new ArrayList<>();
preorder(list, root);
return list;
}
private void preorder(List<T> list, Node root) {
if (root == null) return;
list.add(root.data);
preorder(list, root.left);
preorder(list, root.right);
}

public List<T> inorder() {
throw new UnsupportedOperationException("Todo");
}


public List<T> postorder() {
throw new UnsupportedOperationException("Todo");
}
public List<T> levelorder(){
List<T> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node n = queue.poll();
if (n != null) {
list.add(n.data);
queue.offer(n.left);
queue.offer(n.right);
}
}
return list;
}
// return a string of the binary tree representation
// root,
// left subtree,
// right subtree
// x means null.
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
if (root == null)
sb.append("x");
else {
sb.append(root.data).append("\n");
toString(root.left, 1, sb);
toString(root.right, 1, sb);
}
return sb.toString();
}
private void toString(Node root, int level, StringBuilder sb){

String format = "%" + (level * 4) + "s\n";
if (root == null) {
sb.append(String.format(format, "x"));
} else {
sb.append(String.format(format,root.data.toString()));
toString(root.left, level+1, sb);
toString(root.right, level+1, sb);
}
}



public void printTree() {
printTree(root, null, false);
}

private static class Trunk{
Trunk prev;
String str;
Trunk(Trunk prev, String str){
this.prev = prev;
this.str = str;
}
}

private void showTrunks(Trunk p){
if (p==null) return;
showTrunks(p.prev);
System.out.print(p.str);
}

private void printTree(Node root, Trunk prev, boolean
isLeft){

if (root == null) return;

String prevStr = " ";

Trunk trunk = new Trunk(prev, prevStr);

printTree(root.right, trunk, true);

if (prev==null){
trunk.str="———";
} else if (isLeft){
trunk.str = ".———";
prevStr = " |";
} else {
trunk.str= "`———";
prev.str=prevStr;
}
showTrunks(trunk);
System.out.println(root.data);
if (prev!=null){
prev.str = prevStr;
}
trunk.str = " |";
printTree(root.left, trunk, false);
}

}