Antud on tasakaalus kahendpuu, mille kõik harud on sama pikkusega. Puu

iga tipu x puhul tuleb arvutada teatava funktsiooni g(x) väärtus ning

kirjutada see tippu x, käies niimoodi läbi kõik puu tipud. On teada, et

funktsiooni g(x) väärtuse arvutamise keerukus on võrdeline suurusega

min(x-i vasaku alampuu lehtede arv, x-i parema alampuu lehtede arv)

Mis on kahendpuu kõigi tippude väärtustega täitmise keerukus olenevalt

kahendpuu tippude arvust n?