The following algorithm represents one way of finding the depth of a node in an

Question

The following algorithm represents one way of finding the depth of a node in an
instance of our LinkedTree class. The recursive depthInTree() method takes two
parameters – a key and the root of a tree/subtree – and it returns the depth in that
tree/subtree of the node with the specified key. The separate depth() method
returns the depth in the entire tree of the node with the specified key. If the key is
not found, both methods return -1.
public int depth(int key) {
if (root == null) // root is the root of the entire tree
throw new IllegalStateException(“the tree is empty”);
return depthInTree(key, root);
}
private static int depthInTree(int key, Node root) {
if (key == root.key)
return 0;
if (root.left != null) {
int depthInLeft = depthInTree(key, root.left);
if (depthInLeft != -1)
return depthInLeft + 1;
}
if (root.right != null) {
int depthInRight = depthInTree(key, root.right);
if (depthInRight != -1)
return depthInRight + 1;
}
return -1;
}

If the tree is a binary

subtrees that couldn’t contain the specified key. Like the original version of the

method above, your revised method should also be recursive.

of the ways in which the keys are arranged in the tree. Write a revised version

of

Explanation / Answer

In a binary search tree the left sub-tree always contains nodes less than the root node and the right subtree always contains nodes greater than the root node. The simple modification below will ignore the subtree that does not contain the key being searched for.

public int depth(int key) {
if (root == null) // root is the root of the entire tree
throw new IllegalStateException(“the tree is empty”);
return depthInTree(key, root);
}
private static int depthInTree(int key, Node root) {
if (key == root.key)
return 0;
if (root.left != null && key < root.key) {
int depthInLeft = depthInTree(key, root.left);
if (depthInLeft != -1)
return depthInLeft + 1;
}
if (root.right != null && key > root.key) {
int depthInRight = depthInTree(key, root.right);
if (depthInRight != -1)
return depthInRight + 1;
}
return -1;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.