Question

The average time required to search an element in a binary search tree having n elements

Answer 1

Explanation:

use case diagram and identify the actors for the situations (i) do (ii) as directed:

(i) A repair can be made by a master, a trainee or any other repair shop employee.

(ii) Consider an ATM system. Identify at least three different actors that interact with this system.

Answer 2

The average time required in a search operation in a binary search tree having n elements is O(log n) or O(h) wherever the height of the BST is.

Explanation:

• BST may be a special form of the binary tree within which the left child of a node has a value less than the parent and the right child has price larger than a parent.
• Whenever an element is to be searched, begin looking out from the root node.
• Then if the data is a smaller amount than the key-value, search for the element within the left subtree. Otherwise, search for the element within the right subtree.

Therefore, searching in a binary search tree has an Average case complexity of O(log n) or O(h) wherever h is the height of the BST.