Consider a binary search tree implemented in Java with a node inner class as shown. The tree is implemented as a full binary tree where internal nodes store keys and external nodes are dummy leaves containing null in their key and value fields. Several standard methods have been implemented as discussed in class, but are not shown below. Complete the implementation of the method getMaximum() which must return the value of the largest key in the binary search tree, by filling in the blanks. public class BinarySearchTree ,V> { private static class Node { private V value; private K key; private Node left; private Node right; private Node parent; private Node(K key, V value) { this.value = value; this.key = key; left = null; right = null; parent= null; } } private Node root = new Node(null,null); // initializes an empty tree with dummy leaf // Assume we have implemented methods: V search(K key); insert(K key, V value); // V delete(K key); boolean isExternal(Node node); int size(); etc. public K getMaximum() { if (isExternal(root)) return null; Node current = root; while (________________________ ) { _________________________ ; } return __________________ ; } }
Consider a binary search tree implemented in Java with a node inner class as shown. The tree is implemented as a full binary tree where internal nodes store keys and external nodes are dummy leaves containing null in their key and value fields. Several standard methods have been implemented as discussed in class, but are not shown below. Complete the implementation of the method getMaximum() which must return the value of the largest key in the binary search tree, by filling in the blanks.
public class BinarySearchTree <K extends Comparable<K>,V> {
private static class Node<K,V> {
private V value;
private K key;
private Node<K,V> left;
private Node<K,V> right;
private Node<K,V> parent;
private Node(K key, V value) {
this.value = value;
this.key = key;
left = null;
right = null;
parent= null;
}
}
private Node<K,V> root = new Node<K,V>(null,null);
// initializes an empty tree with dummy leaf
// Assume we have implemented methods: V search(K key); insert(K key, V value);
// V delete(K key); boolean isExternal(Node<K,V> node); int size(); etc.
public K getMaximum() {
if (isExternal(root)) return null;
Node<K,V> current = root;
while (________________________ ) {
_________________________ ;
}
return __________________ ;
}
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
