Przy założeniu, że \alpha jest różna, dla każdego miejsca.

Zielone to liście.

Jeżeli skonstruujemy drzewo w taki sposób, jak na rysunku, to widzimy, zę w każdym punkcie niezmiennik jest spiełniony.
W każdym wierzchołku, który ma synów, dokonujemy podziału pozostałych elementów w stosunku (k-1):1.

Ścieżka jest liniowej długości, bo ma długość około 0.5n = O(n), czyli jest długa.