wooe test

Question

In what order we should insert the following elements into an empty AVL tree so that we don’t have to perform any rotation on it.  

                                      1, 2, 3, 4, 5, 6, 7

A. 4, 2, 1, 6, 3, 5, 7

B. 4, 2, 6, 1, 3, 5, 7

C. 6, 4, 5, 7, 1, 2, 3

D. 4, 5, 3, 2, 1, 6, 7

Comments

4 2 6 1 3 5 7

---

4,2,6,1,3,5,7 option B)

---

ans is correct

Answer 1

option B

Answer 2

AVL Tree was the first balanced Binary Search Tree (BST). AVL tree is a Binary Search Tree, which is balanced with respect to the height of sub-trees.So, it is a height-balanced tree.

A Binary Search Tree is a binary tree in which

• The keys in the left sub tree are smaller than the key in the root
• The keys in the right sub tree are larger than the key in the root
• Left and right sub trees are also Binary Search Trees.

Now, in what order we should insert the {1,2,3,4,5,6,7} elements into an empty AVL tree so that we don’t have to perform any rotation on it.

The order should be $\color{green}{\{4,2,6,1,3,5,7\}}$

In the above tree, the keys of the $\color{purple}{left-sub \hspace{0.1cm}tree\hspace{0.1cm} are\hspace{0.1cm} smaller\hspace{0.1cm} than\hspace{0.1cm} the\hspace{0.1cm} key\hspace{0.1cm} in\hspace{0.1cm} the \hspace{0.1cm}root}$ & $\color{purple}{the\hspace{0.1cm} keys\hspace{0.1cm} in\hspace{0.1cm} the\hspace{0.1cm} right\hspace{0.1cm} sub-tree\hspace{0.1cm} are\hspace{0.1cm} bigger\hspace{0.1cm} than\hspace{0.1cm} the\hspace{0.1cm} keys\hspace{0.1cm} in\hspace{0.1cm} the\hspace{0.1cm} root.}$

So, it is a Binary Search Tree.

The above tree is also height-balanced . ∴ It is a AVL tree.