What does the following mystery method do? Give a very short description of what

Question

What does the following mystery method do? Give a very short description of what the

method returns (not how it does it). Assume the Node is a binary search tree and make sure

this is relevant to your answer.

class Node {

int value;

Node left;

Node right;

static int mystery(Node n) {

if(n==null)

throw new IllegalArgumentException();

if(n.left == null)

return leftmost(n.right);

if(n.left.left == null && n.left.right == null)

return n.value;

return mystery(n.left);

}

// return leftmost descendant of n

static int leftmost(Node n) {

if(n==null)

throw new IllegalArgumentException();

if(n.left == null)

return n.value;

return leftmost(n.left);

}

}

Explanation / Answer

Mystery will return leaf node which was leftmost in the tree. That node might rweside on left subtree or right subtree. This method will start checking from root then continues checking the left subtree and also in right subtree. It will search recursively for the node untill it finds the node which has no child and resides left of its parent. Finally after finding that node it will return value stored in that node.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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