Consider the binary search tree (BST) below, where each node has a label. Note t
ID: 3807925 • Letter: C
Question
Consider the binary search tree (BST) below, where each node has a label. Note that the label is NOT the key. The keys satisfy the BST property. Assume that the keys are distinct: Select all the statements below which are TRUE: Assuming all the keys are distinct, the minimum key is N3 and the maximum key is N8. The key of the node N9 is less than or equal to the keys of nodes N10 and N7. The height of the is 6. The successor of node N4 is N1. The predecessor of node N10 is N9. The list of nodes in the in order-tree-walk is N1, N2, N6, N3, N4, N7, N8, N5, N9, N10, N11, N12Explanation / Answer
1. Assuming all the keys distinct, the minimum key is N3 and maximum key is N8. To find the minimum key, traverse the left nodes of bst. By traversing we get N3 as minimum key and to find maximum key, traverse right nodes and the right most child of bst is maximum key. By this we get, N8 as maximum key.
2. The key of node N9 is less than or equal to the keys of nodes N10 and N7. As key N9 is left child of N7 so it is the property of bst that elements smaller than root will be inserted to left of x and greater than x are inserted to the right of x. So, by this property, it can be said that N9 is less than or equal to N10 and N7.
3. The height of this bst is 6 as height is defined as the number of nodes in the longest path from the root node to a leaf node.
Note: The next three statements are false as successor can be found out if current node has right child, then successor is minimum in right subtree of current node. As this condition is false, so it is not true.
To determine predecessor, the roles of left and right are exchanged and with roles of maximum and minimum exchanged. So, given condition is false.
Inorder traversal is left, root, right. The inorder traversal will be:- N3,N2,N5,N4,N1,N11,N12,N9,N7,N10,N6,N8. So, this condition is also false.