Please leave comments on codes that you input

class LookUpBSTextends Comparable, V> {

//-------------------------------------------------------------

// DO NOT EDIT ANYTHING FOR THIS SECTION EXCEPT TO ADD JAVADOCS

//-------------------------------------------------------------

//bad practice to have public inst. variables, but we want to test this...

//Root of tree

public Node root;

// size of the tree (the number of nodes)

public int size;

public int size() { return size; }

//provided binary tree node class

//bad practice to have public inst. variables,

//in a public nested class, but we want to test this...

public static class Node {

K key; // sorted by key

V val; // associated data

Node left, right; // left and right subtrees

public Node(K key, V val) {

this.key = key;

this.val = val;

}

public Node(K key, V val, Node l, Node r) {

this.key = key;

this.val = val;

this.left = l;

this.right = r;

}

}

//-------------------------------------------------------------

// END OF PROVIDED "DO NOT EDIT" SECTION

//-------------------------------------------------------------

//-------------------------------------------------------------

// You can NOT add any instance/static variables in this class.

// You can add methods if needed but they must be PRIVATE.

//-------------------------------------------------------------

public boolean contains(K key) {

// Return true if key is in tree;

// return false if key is not in tree or if key is null.

// O(H): H as the tree height

return false;

}

public V get(K key) {

// Return the value associated with the given key if the key is in tree

// Return null if the key is not in tree

// throw IllegalArgumentException if key is null

// O(H): H as the tree height

return null;

}

public boolean put(K key, V val) {

// Insert key, val into tree.

// If key is in tree, replace already existing value for this key with the given parameter val

// Return false if key, val cannot be added

// (null keys).

// Return true for a successful insertion.

// O(H): H as the tree height

return false;

}

public static K findBiggestKey(Node t) {

// Return the biggest key in the tree rooted at t.

// Return null if tree is null.

// O(H): H as the tree height

return null;

}

public int height() {

// Return the height of the tree.

// Return -1 for null trees.

// O(N): N is the tree size

return 0;

}

public int numLeaves() {

// Return the number of leaf nodes in the tree.

// Return zero for null trees.

// O(N): N is the tree size

return 0;

}

public String toString() {

// Returns a string representation of the tree

// Change the function call below to

// toStringInOrder: to see (IN-ORDER) string representation of LookUpBST while in debug mode

// toStringLevelOrder: to see (LEVEL-ORDER) string representation of LookUpBST in level-order traversal while in debug mode

return toStringInOrder(this.root);

}

private String toStringInOrder(Node t){

// Follow IN-ORDER traversal to include data of all nodes.

// Example 1: a single-node tree with the root data as "a:112":

// toString() should return a:112

//

// Example 2: a tree with four nodes:

// d:310

// / \

// a:112 p:367

// /

// f:330

// toStringInOrder() should return a:112 d:310 f: 330 p:367

if (t==null)

return "";

StringBuilder sb = new StringBuilder();

sb.append(toStringInOrder(t.left));

sb.append(t.key);

sb.append(":");

sb.append(t.val);

sb.append(" ");

sb.append(toStringInOrder(t.right));

return sb.toString();

}

private String toStringLevelOrder(Node t) {

// Follow LEVEL-ORDER traversal to include data of all nodes.

// Example: a tree with four nodes:

// d:310

// / \

// a:112 p:367

// /

// f:330

// toStringLevel() should return

// d:310

// a:112 p:367

// null null f:330 null

StringBuilder sb = new StringBuilder();

int capacity = (int)Math.pow(2,size()+1)-1;

Node[] list = new Node[capacity];

list[0] = root;

int count = 0;

int level = 0;

for(int i = 0; i < capacity; i++) {

if(i == Math.pow(2,level+1)-1) {

if(count == size) break;

level++;

sb.append(" ");

}

if(list[i] == null) {

sb.append("null ");

}

else {

count++;

sb.append(list[i].key);

sb.append(":");

sb.append(list[i].val);

sb.append(" ");

if((i*2)+1 < list.length) {

list[(i*2)+1] = list[i].left;

list[(i*2)+2] = list[i].right;

}

}

}

return sb.toString();

}

//-------------------------------------------------------------

// Main Method For Your Testing -- Edit all you want

//-------------------------------------------------------------

public static void main(String[] args) {

LookUpBST t = new LookUpBST();

//build the tree / set the size manually

//only for testing purpose

Node node = new Node<>("a", 112);

Node node2 = new Node<>("f", 330);

node2 = new Node<>("p", 367, node2,null);

node = new Node<>("d", 310,node,node2);

t.root = node;

t.size = 4;

// Current tree:

// d:310

// / \

// a:112 p:367

// /

// f:330

//System.out.println(t.toString());

//checking basic features

if (t.root.key == "d" && t.contains("f") && !t.contains("z") && t.height() == 2){

System.out.println("Yay 1");

}

//checking more features

if (t.numLeaves() == 2 && LookUpBST.findBiggestKey(t.root)=="p"){

System.out.println("Yay 2");

}

t = new LookUpBST();

if (t.put("d", 310) && !t.put(null, null) && t.size()==1 && t.height()==0

&& t.put("a", 112) && t.put("p", 367) && t.put("f", 330)

&& t.get("p") == 367){

System.out.println("Yay 3");

}

if (t.size()==4 && t.height()==2 && t.root.key == "d" &&

t.root.left.key == "a" && t.root.right.key== "p"

&& t.root.right.left.key == "f"){

System.out.println("Yay 4");

}

// more insertion

t.put("s", 465);

t.put("e", 321);

t.put("b", 211);

// d:310

// / \

// a:112 p:367

// \ / \

// b:211 f:330 s:465

// /

// e:321

if (t.size()==7 && t.height() == 3

&& LookUpBST.findBiggestKey(t.root.left) == "b"){

System.out.println("Yay 5");

}

// Uncomment the following lines to see an IN-ORDER and a LEVEL-ORDER string representation of the tree, in that order.

//System.out.println(t.toStringInOrder(t.root));

//System.out.println(t.toStringLevelOrder(t.root));

}

}