Question

Consider we constructed binary search tree shown below starting with an empty tree and elements 2, 7, 12, 14, 15, 20, 25, 28, 30 and 40 are come in any order:

Which of the following about the order of elements in input sequence can be true?

• A. 25 comes before 28 and 14 comes after 15
• B. 12 comes before 7 and 2 comes after 7
• C. 20 comes before 7 and 12 comes after 7
• D. 28 comes after 25 and 20 comes after 7

Answer 1

The correct option is C 20 comes before 7 and 12 comes after 7

We know that 'a' comes before 'b' iff 'b' is child of 'a' and 'b' comes after 'a' iff 'b' is child of 'a'.
Option (a) 7 is not the child of 12. So false
Option (b) 20 is not child of 7. So false
Option (d) 14 is not child of 15. So false
Only option (c) is correct i.e. '7' is child of '20' and '12' is child of '7'.