COSC 311 EXAM 3 BST

write the constructors for a bst

public class BinarySearchTree<E extends Comparable<E>>{
public class Node{
E key;
Node left, right;
public Node(E item){
key = item;
left = null;
right = null;
}
}
Node root;
public BinarySearchTree(){
root = null;
}
}

Write the public method for inserting a key

public void insert (E key){
root = insert(root, key);
}

write the private method for inserting a key

private Node insert(Node root, E key){
if (root == null){
return new Node(Key);
}
if(key.compareTo(root.key) < 0){
root.left = insert(root.left, key);
}
else if(key.compareTo(root.key) > 0){
root.right = insert(root.right, key);
}
return root;
}

write the maxvalue method for a bst

private E maxValue(Node root){
E maxv = root.key;
while(root.right != null){
maxv = root.right.key;
root = root.right;
}
return maxv;
}

write the public remove method for bst

public void remove(E key){

root = remove(root, key);
}

write the private remove method

private Node remove(Node root, E key){
if(root == null){
return root;
}
if (key.compareTo(root.key) < 0){
root.left = remove(root.left, key);
}
else if(key.compareTo(root.key) > 0){
root.right = remove(root.right, key);
}
else{
if (root.left == null){

return root.right;

}

else if(root.right == null){
return root.left;
}
root.key = maxValue(root.left);
root.left = remove(root.left, root.key)
}
return root;
}

Write the whole bst code.

public class BinarySearchTree<E extends Comparable<E>>{ public class Node{ E key; Node left, right; public Node (E item){ key = item; left = null; right = null; } } Node root; public BinarySearchTree(){ root = null; } public void insert (E key){ root = insert(root, key); } private Node insert (Node root, E key){ if (root == null){ return new Node(key); } if(key.compareTo(root.key) < 0){ root.left = insert(root.left, key); } else if(key.compareTo(root.key) > 0){ root.right = insert(root.right, key); } return root; } private E maxValue(Node root){ E maxv = root.key; while(root.right != null){ maxv = root.right.key; root = root.right; } return maxv; } public void delete(E key){ root = delete(root, key); } private Node delete(Node root, E key) { if (root == null) { return root; } if (key.compareTo(root.key) < 0) { root = delete(root.left, key); } else if (key.compareTo(root.key) > 0) { root = delete(root.right, key); } else { if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } root.key = maxValue(root.left); root.left = delete(root.left, root.key); } return root; } }