How to correctly populate a binary tree if the keys match?

Question

C++ / C#

How should the binary tree behave if, when entering data from the keyboard, the entered key matches a key that is already stored in the binary tree? What is the best way to solve this problem? The question is general, but arose when performing a specific task:

task

Автоматизированная информационная система на железнодорожном вокзале со­держит сведения об отправлении поездов дальнего следования.
Для каждого поезда указывается:
* номер поезда;
* станция назначения;
* время отправления.
Данные в информационной системе организованы в виде двоичного дерева.
Написать программу, которая:
* обеспечивает первоначальный ввод данных в информационную систему и фор­мирование двоичного дерева;
* производит вывод всего дерева;
* вводит номер поезда и выводит все данные об этом поезде;
* вводит название станции назначения и выводит данные о всех поездах, следу­ющих до этой станции.
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.