Let T be a binary search tree (BST) with n distinct keys. Select all the stateme
ID: 3809053 • Letter: L
Question
Let T be a binary search tree (BST) with n distinct keys. Select all the statements below which are TRUE: In TREE-DELETE (T, z), if z has 2 children then z is replaced by its successor. In the INORDER-TREE-WALK (x), the keys are printed in monotonically decreasing order. For a balanced BST (all leaves have the same depth) with n nodes, the height is h = Theta (n). In TRANSPLANT (T, u, v), u's parent becomes v's parent the successor of a node x is the node with the smallest key greater than x. key. In the TREE-INSERT (T, z), the node is always inserted as a child of the minimum key node.Explanation / Answer
1) True. In TREE-DELETE(T,z) if the node to be deleted has two child nodes,we replace it with the smallest element greater than the value of z, which is the inorder-successor of the tree.
2) False. In a binary searc tree, data on left subtree is always smaller than data on root.Also data on right subtree is always greater than the data on root. Now since root data is always between left subtree and right subtree data in an inorder walk, performing inorder traversal on a binary search tree produces a sorted list in increasing order
3)False. Let us assume that height of tree is h and no. of nodes = N(h) with a height h for a balanced BST. To get the minimum number of nodes with height h,we should fill the tree with as minimum nodes as possible. That means both subtrees are filled till height (h-1). This gives us the reccurence relation: N(h) = 2N(h-1) +1 . Solving the reccurrence we get N(h) = O(2h) . Now since N(h) = n it implies that n = O(2h) => h = O(log n).
4) True. The TRANSPLANT(T,u,v) function tries to replace the node u and its corresponding subtree with some other node v and its subtree. Hence in order to replace u's position with v's position, their parents must also be updated as each others parents.
5) True. As explained in part 2, we get a sorted list of elements in the Inorder walk of a BST. Hence the successor of the element x is the node with the smallest key greater than the value of x.key.
6) False. No it is not the case. While inserting a node in a BST we need to find a location for the new node. While finding the location if the data already exists, we can ignore it and come out. Otherwise insert data on the last location of the path traversed i.e. as a child node of the last node in the traversed path, it need not be the minimum key node.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.