Дистанционный практикум по программированию

Одним из способов представления множеств в памяти компьютера является простое (несбалансированное) двоичное дерево поиска. Каждый узел данного дерева может иметь не более двух детей (левый и правый сын).

Вставка нового элемента x в дерево начинается с корневого узла. Сравним x с ключом в корне. Если они равны, то делать ничего не надо – элемент уже содержится в дереве. Если x меньше ключа в корне, то идём в левое поддерево, если больше – в правое. Продолжаем делать так до тех пор, пока идти станет больше некуда – в этом случае создаётся новый листовой узел.

На рисунке показано дерево, полученное из пустого дерева после вставки элементов 8, 5, 7, 11, 9, 3, 6.

Высотой дерева называется длина максимального пути от корня до листа. Например, для дерева на рисунке высота равна 3, так как путь от от корня до листа с ключом 6 имеет длину 3.

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