В двоичном дереве на единицу меньше узлов, чем листьев, потому что при добавлении узла в дерево количество узлов и листьев либо не меняется, либо увеличивается на 1. 1

Это следует из того, что если узел добавляется к узлу с 0 дочерними элементами, то единственный узел с двумя дочерними элементами и количество листьев не меняются. 1 Если же узел добавляется к узлу с дочерним элементом, то количество узлов с двумя дочерними элементами и количество листьев увеличивается на 1. 1

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

Также в полном бинарном дереве количество внутренних узлов на единицу меньше количества листьев. 2 Это следует из того, что на нулевом уровне имеется 2 0 узлов, на первом — 2 1, на втором — 2 2 и т. д.. 2 На первых k-1 уровнях количество узлов составляет 1 + 2 + 4 + … + 2 k-1 = 2 k-1, а на уровне k количество узлов 2 k, то есть ровно на один больше. 2