2 added 55 characters in body
source | link

So what is correct interpretation of this question?

Somehow, if we try to generalize, I feel this question boils down to following:

Somehow, if we try to generalize, I feel this question boils down to following:

So what is correct interpretation of this question?

Somehow, if we try to generalize, I feel this question boils down to following:

1
source | link

Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows:

We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there are fewer than 15 elements, we have some flexibility as to the structure of the tree. Which letters can appear at the root? For each possible root, which letters can be the left child of the root? The right child? Find the true statement in the list below.

  1. G cannot be the root.
  2. It is not possible for B to the left child of the root and K the right child of the root of the same tree.
  3. It is not possible for B to the left child of the root and J the right child of the root of the same tree.
  4. It is not possible for D to the left child of the root and K the right child of the root of the same tree.

I selected the option 2, and it was correct. However after some thinking I felt option B is also incorrect. And in fact now I am more confused with the meaning of the question itself.

First I am unable to fix what of the question is asking:

  • Given option is correct if with given option, we can build a valid BST of height 4 (considering root is at height 0)
  • Given option is correct if with given option, we cannot build a valid BST of height less than 4.

Should we call option 1 correct as we can build height 4 BST with root G as follows:

         G
       /  \
      /    \
     /      \
    D        I
   / \      / \
  B   F    H   L
 / \ /        / \
 A C E       K   M
            /     
           J

or call incorrect since we can build height 3 (<4) BST with root G as follows:

         G
       /  \
      /    \
     /      \
    D        J
   / \      / \
  B   F    I   L
 / \ /    /   / \
 A C E    H   K M

Similarly I initially thought that there are 8 characters between B and K. One of them can be root. So 7 characters are remaining, with which we can build only 4-height BST. We cannot build BST with height less than 4. So somehow thinking this much I selected option 2. However, option says "It is not possible...". But it is vey much possible to build height 4 tree with B as left child and K as a right child of the root:

         G
       /  \
      /    \
     /      \
    B        K
   / \      / \
  A   D    I   M
     / \  / \ / 
    C   F H J L 
       /    
      E    

Similarly I can build height-4 tree with B as left child and J as right child of the root (as said not possible in option 3):

         G
       /  \
      /    \
     /      \
    B        J
   / \      / \
  A   D    I   L
     / \  /   / \ 
    C   F H   K M
       /    
      E    

Finally, I can build height-4 tree with D as left child and K as right child of the root (as said not possible in option 4):

           G
         /  \
        /    \
       /      \
      D        K
     / \      / \
    C   F    I   M
   /   /    / \ / 
  B   E     H J L
 /           
A 

Somehow, if we try to generalize, I feel this question boils down to following:

Whether the minimum and maximum height of the binary search tree is constrained, if we fix certain elements of the binary search tree to particular position (as in this case the immediate children of the root)?