Question

Consider the AVL Tree built by inserting the following sequence of integers, one at a time: 5, 2, 8, 7,9 Then we insert 11. After we insert 11, before we perform any necessary rotations, is the tree balanced? And if not, which is the root of the lowest imbalanced subtree? (a) None, since the tree is already balanced after inserting 11. (b) The node containing 5. (c) The node containing 8. (d) The node containing 11. (e) The node containing 7.

Answer 1

1.

Step 1 :

The first element to be inserted is 5.

5

Step 2 :

The next element to be inserted is 2.

5 2

Step 3 :

The next element to be inserted is 8.

5 2 8

Step 3 :

The next element to be inserted is 7.

5 2 8 7

Step 4 :

The next element to be inserted is 9.

5 8 2 7 9

Step 4 :

The next element to be inserted is 11.

5 8 2 7 9 11

This would cause the tree to be unbalanced because node 5 will have a balance factor of -2.

Thus, the correct answer is option b.

2.

The given preorder traversal is V P G U X Y

In a binary search tree, the inorder traversal is always in sorted order.

So, the inorder traversal is G P U V X Y

The first element of preorder traversal is always the root of the tree.

V is the root of the tree.

V

So, the left and right subtree of V is divided as :

Left	Root	Right
G P U	V	X Y

The next element in preorder traversal is P and it is in the left subtree of root V.

The tree becomes :

V Р

The next element in preorder traversal is G and G is to the left of P in inorder traversal.

The tree becomes :

V Р G

The next element in preorder traversal is U and U is to the right of P in the inorder traversal.

V Р с G

The next element in preorder traversal is X and it is to the right of root element V..

The tree becomes :

V Х P G U

The next element in preorder traversal is Y and it is to the right of X in inorder traversal.

The tree becomes :

V X Р Y G U

So, the final tree is :

V X Р Y G U

The following steps are used to find the postorder traversal.

• Start from the root and traverse towards the left until a node with no right child occurs.
• The node selected is G. So, G is the first node in the postorder traversal.
• Backtrack from node G to its parent P. Move to the right child U which is already a leaf.
• The next node in the postorder traversal is U.
• Backtrack from node U to its parent P. Since all the descendents of P have been visited, the next node in the postorder traversal is P.
• Backtrack from P to its parent V. Move to its right child X and traverse the subtree until a node with no right child is found.
• The node selected is Y.  The next node in the postorder traversal is Y.
• Backtrack from node Y to its parent X. Since all the descendents of X have been visited, the next node in the postorder traversal is X.
• Backtrack from X to its parent V. Since all the descendents of V have been visited, the next node in the postorder traversal is V.

Thus, the postorder traversal is :

G U P Y X V

For the level order traversal,

Level 1 visits the node V from left to right.

Level 2 visits the nodes P and X from left to right.

Level 3 visits the nodes G, U and Y from left to right.

Thus, the level order traversal is :

V P X G U Y.