Q127: Height imbalance in AVL trees

Question #127: AVL trees are an example of height balanced binary search trees where height difference between the left and the right child of any node is at most 1. Check out the tree below and decide which of its nodes have height imbalance.

Options:

1. Node 5
2. Nodes 5 and 8
3. Nodes 5, 8 and 12
4. Nodes 5, 8, 12 and 10

Solution: The correct option is second one.

For node 5, diff between the heights of left & right subtrees is |2-4| = 2 which is greater than 1.

For node 12, diiff between the heights of left & right subtrees is |2-1| = 1 which is well within the limits.

So we can see that only nodes 5 & 8 are unbalanced.

Q112: Properties of Binary Search Trees

Question #112: Which of the following is true about BST (Binary Search Trees)?

I. If the inorder traversal of any binary tree is sorted in increasing order, then the tree must be a BST.

II. BSTs are an example of height balanced trees.

Options:

1. Both I and II
2. Only I
3. Only II
4. Neither I, nor II

Solution: The correct answer is 2nd one. It’s a property of BST that the inorder traversal will always be sorted. The opposite is also true, as any tree whose inorder traversal is sorted, follows the BST property that

LeftChild < Root < RightChild.

Also note that BST have no height balancing properties. The structure of the BST depends on the order in which the keys were inserted in the tree. The following tree would be created if elements are inserted like this: 1,2,4,3,5,6,8.