Q: Take the BSTR class that is on blackboard and add a recursive method, int dep
ID: 3732271 • 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.
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
int depth(struct TreeNode node)
{
if (node==NULL)
return 0;
else
{
int ldepth = depth(node.left);
int rdepth = depth(node.right);
if (ldepth > rdepth)
return(ldepth+1);
else
return(rdepth+1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.