Discussion
Let P be the set of all integers from 1 to 15. Consider any order of insertion of the elements of P into a binary search tree that creates a complete binary tree.
Which one of the following elements can NEVER be the third element that is inserted?
Answer: D
The element that can never be third is 5.
The only complete binary search tree on 1 to 15 has root 8, then 4 and 12, then 2, 6, 10 and 14, and the odd numbers as leaves. In a BST every node must be inserted after all its ancestors, so the first element is 8 and the second is 4 or 12.
The third element can therefore be the other child of the root, or a child of the second element: 4 (order 8, 12, 4), 2 (8, 4, 2) and 10 (8, 12, 10) are all possible.
5 sits on the fourth level, below 8, 4 and 6, so at least three elements must come before it, and it can be inserted fourth at the earliest.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development