0 votes

$A)$ Rotation operation of AVL tree always preserves the inorder numbering.

$B)$ If every node of BST has either $0$ or $2$ children , then searching time is $O(log n)$

Which statement is correct?

Given $A)$ is correct but $B)$ is not. Plz explain how?

3 votes

Best answer

A. Rotation in AVL trees , keeps the AVL tree still a binary search tree , thus the inorder numbering doesn't change .

B. Let's come to the second statement , the description given is of a full binary tree.

Now if we imagine a full binary tree ,

In binary search tree , we know that time to search is $O(h)$ , where $h$ is the height of the binary tree.

Let's calculate the height in this case of full binary tree,

Total number of nodes = $n = 1+2+2+2+.... h$ times (2 nodes at each level) = $1+2h$.

$1+2h=n => h=\frac{n-1}{2}$ .

Thus in this case , time to search = $O(h) = O(\frac{n-1}{2}) = O(n).$

Thus the statement is false.