Can you please let me know if my answer if correct. If not, why with corrections
ID: 3825478 • Letter: C
Question
Can you please let me know if my answer if correct. If not, why with corrections. Please and thank you.
3) For a key k that is not found in a binary search tree T, prove that both the greatest key less than k and the least key greater than k lie on the path traced by the search for k. When we search for a key in Binary search tree, we start from the root and check if root is equal to the key. If not, then if the key is greater than the root, we go to its right subtree and if it is less than the root, we go to the left subtree. This goes on until we find the key or find that key does not exist. Now, there are 2 cases in the end when we find out that key does not exist: i) First case: Key is greater than current node, we go right and the key is less than the right child. In this case the current node is the greatest element less than key and right child is least element greater than key. Therefore both are visited. ii) Second case: Key is less than current node, we go left and the key is greater than the left child. In this case the current node is the least element greater than key and left child is greatest element less than key. Therefore both are visited. In both the cases, both elements are visited. Hence proved.
Explanation / Answer
public class BST {
private static class Node
{ private int data; private Node left, right; public Node(int value)
{ data = value; left = right = null;
}
} private
Node root;
public BST()
{ root = null;
} public Node getRoot() {
return root;
}