You are given a binary search tree below and a Main class that make use of the binary search tree. For this assignment,

[answerhappygod]

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);
}

}