Бинарные деревья поиска и рекурсия – это просто

Совершенно верно. В дереве, в отличие от графа количество ребер всегда равно количеству вершин минус 1. То есть количество ребер линейно зависит от количества вершин.