Q: Take the BSTR class that is on blackboard and add a recursive method, int dep
ID: 3734710 • Letter: Q
Question
Q:
Take the BSTR class that is on blackboard and add a recursive method, int depth(), to compute the depth of the tree (the depth is the length of the longest path from the root to a leaf node). Note: you are not allowed to remember the depth in an instance variable – you must compute it each time depth() is called.
PLEASE show main method implementing the depth() working
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 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);
}
}
public int depth()
{
return depth_util(root);
}
public int depth_util(TreeNode temp)
{
// if the current tree is empty
if(temp == null)
return 0;
else
{
// find the height of left subtree
int l = depth_util(temp.left);
// find the height of right subtree
int r = depth_util(temp.right);
if( l >= r )
return l + 1;
else
return r + 1;
}
}
public static void main(String[] args)
{
BSTR<Integer, Integer> ob = new BSTR<Integer, Integer>();
ob.put(10, 2);
ob.put(5, 2);
ob.put(3, 2);
ob.put(15, 2);
ob.put(18, 2);
ob.put(19, 2);
ob.put(8, 2);
System.out.println("Depth : " + ob.depth());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.