Option (C) is True .
Suppose that we need to insert a node $z$ such that $k = key[z]$. Using binary search we find a nil such that replacing it by $z$ does not break the BST-property
BST-Insert$\bf{(x, z, k)}$
- : if $x = nil$ then return “Error”
- : $y \leftarrow x$
- : while true do $\{$
- : if $key[y] < k$
- : then $z \leftarrow left[y]$
- : else $z \leftarrow right[y]$
- : if $z = nil$ break
- : $\}$
- : if $key[y] > k$ then $left[y] \leftarrow z$
- : else $right[p[y]] \leftarrow z$
Time Complexity Analysis :
- Best $Case = O(1)$ , When it is smallest/greatest element and BST contains only all greater/smaller element than inserting element respectively.
- Avg $Case = O(\log n)$ , When it belongs between some elements .
- Worst $Case = O(n)$ , When it is smallest/greatest element and BST contains only all smaller/greater element than inserting element respectively.