Question

Which of the following statement are correct?
I. In a max heap tree, the minimum value will always lie in one of the leaf node.
II. Worst case time complexity of searching on element in a binary search tree is O(n)
III. In an AVL Tree, the smallest element can be found in o(log(n)) time.
IV. DFS requires back tracking which is implemented using stack.

• A. I & II
• B. All one correct
• C. I, II & III
• D. II, III & IV

Answer 1

The correct option is B All one correct

I. In a max heap tree, the minimum value amongst the nodes will always lie in one of the leaf node, so this statement is true.
II. Since in the worst case, the BST will be skewed. So problem size will reduce linearly with each step, so the worst case time complexity of searching on element in a binary search tree is o(n), hence this statement is true.
III. Since An AVL Tree never be skewed and it will divide the problem into two equal parts approximately with each step, so the smallest element can be found in o(log(n)) time, hence this statement is true.
IV. Since only stack data structure is used to implement depth first traversal. So this statement is also true.