Let T be a Binary Search Tree (BST) with n keys. Select all the statements below
ID: 3911854 • Letter: L
Question
Let T be a Binary Search Tree (BST) with n keys. Select all the statements below which are TRUE. A tree is balanced if all the leaves have the same depth. The height of a balanced BST T is O (Ig n) If the BST T has height 3, then the maximum number of nodes in T is 16 For any node x, if y is a node in the right subtree of x,and z is a node in the left subtree of x, then y.key s z.key O TREE-SUCCESSOR, TREE-SEARCH, and TREE-MINIMUM have the worst-case running time ? (n). O The first element printed by the POSTORDER-TREE-WALK(?.root) is the smallest key of T TREE-DELETE, TREE-TRANSPLANT, and TREE-INSERT have the worst-case running time ? (A). O The worst-case complexity of the height of a BST T is ? (n).Explanation / Answer
1) False
The a tree is said to be balances if it folllows the three conditions:-
But since the Point says "A tree is balanced if all its leaves have same depth". This cant be the case as a tree is also balanced if one of the left or right subtree has a leaf whoose height is greater by atmost 1 value.
------------------------------------------------------------------------------------------------------------------------
2) False
The maximum number of nodes in a BST with height 3 is 2k - 1 , where k is 3. So it is 7.
-------------------------------------------------------------------------------------------------------------------------
3) False
In a BST the left subtree should always be smaller than the right subtree.
------------------------------------------------------------------------------------------------------------------------
4) True
The given tree is a binary search tree and the time complexity will be O(n) as this happens for left skewed trees.
--------------------------------------------------------------------------------------------------------------------------
5) True
The post order traversal or walk is (Left, Right, Root) so it will print the left most element of the tree.
Since T is a BST, the leftmost element will be the smallest element.
-----------------------------------------------------------------------------------------------------------------------
6) True
Becuase you will have to go the last leaf in order to insert/delete an element.
-------------------------------------------------------------------------------------------------------------------------
7)True
In order to find the height we would have to go through all the nodes. so O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.