Задача с Яндекса
Дается бинарное дерево. Найдите диаметр дерева.

Решение:
Определение: Диаметр в дереве - это максимальное расстояние между двумя вершинами.
Из определения можно понять, что диаметр это максимальный путь между двумя листьями дерева.

Пусть h[v] - максимальное расстояние от вершины v до листа поддерева вершины v. Чтобы посчитать h[v] вы должны написать dfs.
И обновлять h[v] = max(h[v.left], h[v.right]) + 1. Зная массив h как найти диаметр ?
Диаметр обязательно пройдет через какую то вершину. Давайте переберем эту вершину. Пусть эта вершина u, тогда максимальный путь между листьями поддерева вершины u равно h[u.left] + h[u.right] + (2 или 1 или 0 в зависимости сколько детей у вершины u).
Среди всех таких сумм возьмем максимум.
Время работы алгоритма O(n).
Если бы у нас было бы произвольное дерево такой алгоритм не сработал бы, так как могут быть вершины с > 2 потомками..
Кому интересно вот алгоритм нахождения диаметра для произвольного дерева ссылка