# 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


So what is correct interpretation of this question?

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)?

The question you were asked talks about 4 levels, which is a height of 3, not a height of 4.

Answer 1 is incorrect because there is a tree of height 3 in which G is at the root (you provided an example already).

Answer 3 is incorrect because of the following tree:

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


Answer 4 is incorrect because of the following tree:

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


To see this: Assume T is a tree which satisfies the constraints, i.e.

           1
/  \
/      \
/          \
B            K
/   \        /   \
2   3       4     5
/ \ / \     / \   /  \
6  7 8 9   10  11  12 13


Where the numbers 1 to 13 represent unknowns from A,C,D,E,F,G,H,I,J,L,M and two empty symbols.

As you can see, both the left and the right subtree can contain at most 6 elements. Thus, the root has to be $1 \in \{F,G,H\}$.

If $1=F$, then the right sub-tree has to contain {G, H, I, J, K, L, M}. However, K is the root of the right sub-tree and therefore $\{4,10,11\} = \{G,H,I,J\}$, which is impossible. Using symmetrical arguments we can show that the root cannot be H either.

Therefore it must be $1 = G$. But then $\{3,8,9\} = \{C,D,E,F\}$ which is a contradiction as well.