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

Недоліком цього методу є те, що у разі зміни або додавання значень листя у лісі доведеться заново обчислювати значення кореневого вузла, і при великій їх кількості це може призвести до великих обчислювальних витрат. Вирішення цієї проблеми призводить до різних способів побудови дерев аутентифікації; в деяких випадках проводиться додавання нових вузлів у вже існуюче дерево або побудова нових дерев. Детальний опис моделей побудови дерев аутентифікації виходить за рамки цієї книги.