Как поступать в бинарном упорядоченном дереве с повторяющимися элементами? Вешать на правый лист?

Если Вас балансировкой дерева никто не просил заниматься, то не нужно так смущаться, если оно вдруг не получится сбалансированным.

Сбалансированное дерево - оно на практике кое в чем удобнее, да.. . Но не просили ведь.