Задача с собеседования в Яндекс
Дается бинарное дерево. Проверьте является бинарное дерево сбалансированным.

Определение: В сбалансированном дереве высота левого и правого поддерева отличается не более чем на 1.

Решение:
Давайте добавим параметр h в структуре вершины. Которая будет равна глубине вершины относительно корня. Глубину для каждой вершины мы сможем посчитать во время обхода в глубину, просто передавая число которая будет отвечать за глубину и увеличивая ее во время запуска dfs от детей.
Также создадим еще один параметр в структуре вершины, которую назовем maxDeapth, которая будет отвечать за максимальную глубину от левого поддерева и от правого поддерева. Чтобы пересчитать maxDeapth мы первоначально для вершины присваиваем maxDeapth = h, а после берем максимум maxDeapth от детей.
Таким образом мы должны для каждой вершины 'v' проверить неравенство |v.left.maxDeapth - v.right.maxDeapth| <= 1.
Алгоритм работает за O(N)
Псевдокод в комментариях: