Question

17) Which of the following is a valid binary search tree? 23 12 40 19 30 61 13 21 41 50 23 43 10 18 34 51 15 21 40 50 23 43 10 18 51 15 27 40 50 What is the worst-case runtime of searching for a value in a binary search tree? (a) constant O(1) (b) logarithmic O(logn) (c) linear O(n) 18) Pag

Answer 1

17) A binary search tree is a node-based search tree with the following properties:

1. The left subtree of a node contains only nodes with keys less than the node's key

2. The rightt subtree of a node contains only nodes with keys greater than the node's key

3. Both the left and right subtree must also be binary search trees.

So, from this we can say that:

(a) is not a valid binary search tree, as 41 is in the left subtree of 40 which is does not comply.

(b) is a valid binary search tree as it complies with the properties of a binary search tree.

(c) is also not a binary search tree as seen in the left subtree of 23, 27 is present which is greater than 23.

18) The worst case runtime of searching for a value in a binary search tree is O(n)

So option C linear O(n) is true