Question

Q.15 :-What is the expected time required to search for a value in a binary search tree containing n nodes
0(1)​

Answer 1

Answer:

Searching: For searching element 1, we have to traverse all elements (in order 3, 2, 1). Therefore, searching in binary search tree has worst case complexity of O(n). In general, time complexity is O(h) where h is height of BST.

Explanation:

Answer 2

The expected time required to search for a value in a binary search tree containing n nodes is O(logn).

Binary Search Tree

A binary search tree is a data structure where each node has a maximum of up to two children. The left subtree stores keys less than the parent node and the right subtree stores keys greater than the parent node.

In a Binary search tree, Searching depends on the height of the tree.

The time complexity of the Binary search tree:

Binary search in a sorted array is by repeated dividing the search interval in half. Start the search by covering the whole array. If the value of the search key is less than the element in the middle of the interval, then divide the interval of the lower half. Otherwise, divide it into the upper half. Repeatedly check until the value is found in either of the intervals or find an empty interval.

• Let the length of the array = $n$. After iteration 1, the length of the array = $\frac{n}{2}$.
• After iteration 2, the length of the array = $\frac{n}{2} *\frac{n}{2}$
• For k iteration, we get the length of array = $\frac{n}{2^{k} }$
  After k iterations, the length of the array becomes 1
  Therefore, the length of the array = $\frac{n}{2^{k} } =1$
  $n=2^{k}$
  Apply log on both sides:

$log2 (n) = log2^{k} \\log2 (n) = k log(2)$

The  expected time required to search for a value in a binary search tree containing n nodes $k = log (n)$