GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 44

Question

Let $B$ be a binary search tree (BST) with eight nodes filled with the following set of eight integer keys $A=\{10,2,5,3,20,15,9,22\}$. The order in which these keys were inserted to create $B$ is not known. However, it is known that once the BST is created, $(8 \times 9) / 2=36$ comparisons are required to verify if all eight keys of $A$ are present in $B$.

How many leaf nodes are present in B?

Answer 1

no of comparison to check all 8 keys are present or not  = (8 * 9) / 2 i.e. 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8..
i.e.
1st key : 1 comparison
2nd key : 2 comparison
3rd key : 3 comparison
.
.
.
8th Key : 8 comparison
such scenario is possible iff given tree is left skewed..
hence number of Leaf = 1..

Answer 2

Here every element is being compared with every other element and this is worst case scenario in binary search tree for finding an element, so definitely its a skew BST and it has a leaf node = 1

open for any corrections :)