AVL tree

Question

Consider following statements:

S1: Rotation operation in AVL always preserves the Inorder ordering.

S2: The median of all elements in AVL tree is always at root or one of its two children.

S3: If every node in BST has either 0 or 2 children,then searching is O(logn)

S4: In a 3 array tree. If number of internal node is 20 then number of Leaves are 41.

True Statements ?

Ans: Only S1 and S4

Comments

@arvin,

yes bro, we were some times did silly mistakes....

just i want to say it, that's it...

---

Brother, In BST suppose i want to find the time complexity for finding a non existent element in Best case what it would be ? and please explain why ?

---

what is the last statement? can u correct that because i am in a dilemma on that ?

.

.

and it depends on the position of the root element and the structure of the tree.

in some cases it can be O(1) when its linear tree oriented in right side only and say root=3 we have to search for 1 so we can find out in O(1) that it doesnot exist f0r the tree as it has no left child.

while in other it can be O(n) when we are finding the lagrest element and its right side oriented tree as we have to traverse till last element.

Answer 1

• Rotation operation in always preserves the inorder numbering so 1st is true.
• AVL tree doesnot guarantee that both left and right subtree has equal number of nodes, so statement is false.
• Consider