Please zoom in if you have trouble readding the question. Thank You Consider the
ID: 3855158 • Letter: P
Question
Please zoom in if you have trouble readding the question. Thank You
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 all the keys are distinct. Select all the statements below which are TRUE: The height of the BST is 4. The successor of the node N_9 is the node N_3. The key of the node N_1 is less than the key of the node N_9. The list of nodes in the inorder-tree-walk is N_5, N_8, N_4, N_10, N_7, N_11, N_9, N_6, N_3, N_1, N_2. N_6 is the node with the maximum key. The predecessor of the node N_9 is the node N_11. The height of the node N_7 is 1.Explanation / Answer
options which satisfy the BST property and the statement which is true:
1.)The height of the BST is 4
i.e., the number of edges in the longest path from the node to the leaf node(so here the path from the root N11 to the least leaf node N1 and N2 is 4
2.) N6 is the node with the maximum key
i.e., The right subtree of a node contains only nodes with keys greater than the node’s key. so here N6 is highest right subtree, so the key value of N6 is maximum.
options which not satisfy the BST property and the statement which is false:
1.) The key node of N1 is less than the key node of N9
i.e., The right subtree of a node contains only nodes with keys greater than the node’s key. So here right subtree of a node N1 is greater than the N9.
2.) The list of node in inorder-tree-walk is
N5,N8,N4,N10,N7,N11,N9,N6,N3,N1,N2,
solution:
inorder-tree-walk is Inorder (Left, Root, Right)
N5,N8,N4,N10,N7,N11,N1,N3,N2,N6,N9
3.) The height of the node N7 is 1
i.e.,the number of edges in the longest path from the node to the leaf node, but here N& doesn't have any child so the height is 0