Q: Take the BSTR class that is on blackboard and replace the put(K key, V value)
ID: 3732873 • Letter: Q
Question
Q:
Take the BSTR class that is on blackboard and replace the put(K key, V value) method with a recursive method – i.e. one that doesn’t use a loop.
Code:
public class BSTR<K extends Comparable<K>, V>
{
private class TreeNode
{
K key;
V value;
TreeNode left;
TreeNode right;
public TreeNode(K key, V value)
{
this.key = key;
this.value = value;
this.left = null;
this.right = null;
}
}
private TreeNode root;
public BSTR()
{
this.root = null;
}
public void put(K key, V value)
{
if (root == null)
{
TreeNode node = new TreeNode(key, value);
this.root = node;
}
else
{
TreeNode current = root;
while (current != null)
{
int c = key.compareTo(current.key);
// key == current.key
if (c == 0)
{
current.value = value;
return;
}
// key < current.key
else if (c < 0)
{
if (current.left != null)
{
current = current.left;
}
else
{
TreeNode node = new TreeNode(key, value);
current.left = node;
}
}
//c > 0, i.e. key > current.key
else
{
if (current.right != null)
{
current = current.right;
}
else
{
TreeNode node = new TreeNode(key, value);
current.right = node;
}
}
}
}
}
public V get(K key)
{
return getR(key, root);
}
private V getR(K key, TreeNode current)
{
if (current == null)
{
return null;
}
else
{
int c = key.compareTo(current.key);
// key == current.key
if (c == 0)
{
return current.value;
}
// key < current.key
else if (c < 0)
{
return getR(key, current.left);
}
//c > 0, i.e. key > current.key
else
{
return getR(key, current.right);
}
}
}
public int size()
{
return sizeR(root);
}
public int sizeR(TreeNode current)
{
if (current == null)
{
return 0;
}
else
{
return 1 + sizeR(current.left) + sizeR(current.right);
}
}
}
Explanation / Answer
public void put(K key, V value)
{
// modify code to call new function recurPut
recurPut(root, key, value);
}
private void recurPut(TreeNode current, K key,V value) {
// if no node is present then create new one.
if(current == null) {
return new TreeNode(key,value);
}
int c = key.compareTo(current.key);
// if key == current.key
if (c == 0)
{
current.value = value;
return current;
}
//if key < current.key then we must insert into left.
else if(c< 0){
current.left = recurPut(current.left, key, value);
}
//if key > current.key then we must insert into right.
else if(c> 0){
current.right = recurPut(current.right, key, value);
}
// we must return the node as it is since it may be unchanged.
return current;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.