# Made Easy Test Series: Data Structure

195 views

$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?

in DS

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.

selected by
1
Take example of binary heap which is a complete tree but not AVL there searching takes (n) time
0
yes , you're right

## Related questions

1 vote
1
385 views
There is given a infix expression: ${\color{Red} {1}}$ $A+B\times C/\left ( \left ( D+E \right )+F\times G \right )$ While converting infix expression to postfix expression number of symbols in the stack at indicated ${\color{Red} {point-1}}$ infix expression (assume stack is initially empty) ______________ they told $5$, but is it correct? Can anyone give some explanation??
A stack based CPU executes the instruction. Memory location $500$ contain $0X 88$ and memory location $700$ contain $0X37$. The stack pointer is at $0X003F$ The instruction are as follows: $I_{1}:PUSH$ $500$ $I_{2}:PUSH$. $700$ $I_{3}:ADD$ $I_{4}:POP$ ... $0X88$ after execution of instruction. $C)$ Memory location $600$ contain $0XBF$ after execution of instruction. $D)$ Both $a)$ and $c)$