Заметим, что если в бинарном дереве аутентификации содержится t листьев, то при достаточно большом значении t для проведения аутентификации необходимо пройти достаточно большое количество ребер в дереве. Параметр, обозначающий количество ребер на пути от листа до корневого узла, назовем длиной пути. Длина пути аутентификации может быть минимизирована при помощи соответствующего построения дерева аутентификации. Так, если дерево является сбалансированным (любые пути по которому от листа до корневого узла отличаются не больше, чем на единицу), то длина пути аутентификации будет приблизительно равна lg(t).

Недостатком данного метода является то, что в случае изменения или добавления значений листьев в дереве придется заново вычислять значение корневого узла, и при большом их количестве это может привести к большим вычислительным затратам. Решение этой проблемы приводит к различным способам построения деревьев аутентификации; в некоторых случаях производится добавление новых узлов в уже существующее дерево либо построение новых деревьев. Подробное описание моделей построения деревьев аутентификации выходит за рамки данной книги.