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.