1. Сколько различных бинарных деревьев поиска можно построить для ключей 1, 2, 3, 4?

Я насчитал 12.
Здесь их не нарисовать, к сожалению, но, если Вы знакомы с терминологией и определением ключа, попробую объяснить.
1) случай - корень - 1 (таких деревьев 4):
1.1) 1-е дерево: корень - 1; правый сын - 2, левого нет; правый сын вершины 2 - 3, левого нет; правый сын вершины 3 - 4, левого нет.
Это единственное дерево, в котором ключ 2 является сыном ключа 1 - *
1.2) 2-е дерево: корень - 1; правый сын - 3, левого нет; правый сын вершины 3 - 4, левый - 2.
Это единственное дерево, в котором ключ 3 является сыном ключа 1 - *
1.3) 3-е дерево: корень - 1; правый сын - 4, левого нет; левый сын вершины 4 - 2, правого нет; правый сын вершины 2 - 3, левого нет.
1.4) 4-е дерево: корень - 1; правый сын - 4, левого нет; левый сын вершины 4 - 3, правого нет; левый сын вершины 3 - 2, правого нет.
Этими четырьмя деревьями исчерпывается случай, когда корнем является 1 - *
2) случай - корень - 2 (таких деревьев 2)
2.1) 5-е дерево: корень - 2; левый сын - 1, правый - 3; вершина 1 не имеет поддеревьев; правый сын вершины 3 - 4.
2.2) 6-е дерево: корень - 2; левый сын - 1, правый - 4; вершина 1 не имеет поддеревьев; левый сын вершины 4 - 3.
Больше искомых деревьев с корнем 2 нет - *
Деревья с корнями 3 и 4 - зеркальные отражения уже построенных деревьев, т. е. деревьев с корнем 3 - 2, а с корнем 4 - 4. Строятся они так: в первых шести деревьях замените 1 на 4, 2 на 3, 3 на 2 и 4 на 1 (не обращая внимание на то, что числа перестали быть ключами) , а затем полученные деревья отразите зеркально относительно корня.
Для вторых шести деревьев верны аналогичны помеченным звездочкой утверждения.
Все утверждения, помеченные звездочкой (в т. ч. и для второй шестерки деревьев) оставляю для доказательства Вам.
Если что не понятно - пишите на почту.

2Ormandiore: каждый ключ, несомненно, может быть корнем дерева, но кто сказал, что таких случаев - по одному?!

очевидно, четыре, так как каждый ключ может быть вершиной дерева