در پیمایش مثلا میان ترتیب،کاری که صورت میگیره اینه که یک گره(در اینجا ریشه) تکلیفش معلوم میشه و تابعمون به دو قسمت شکسته میشه و.پس می تونیم بگیم که تابع بازگشتی بصورت زیردارد:

[tex]T(n) = T(k) T(n – k – ۱) c[/tex]

حالا توی حالتهای مختلف تابع بالا را در نظر میگیریم:
حالت اول:یکی از زیر درختها خالی و بقیه در دیگری.

[tex]T(n) = T(0) T(n – ۱) c[/tex]

بصورت بازگشتی که بنویسیم داریم:

[tex]T(n) = (n-1)T(0) T(1) (n-1)c[/tex]

با توجه به اینکه پیمایش یک درخت خالی زمان ثابتی خواهد شد. تابع از مرتبه [tex]O(n)[/tex] خواهد بود.
حالت دوم:دو زیر درخت مساوی.

[tex]T(n) = 2T(\left \lfloor \frac{n}2 \right \rfloor ) c[/tex]

که توی این حالت هم طبق قضیه master تابع از مرتبه [tex]O(n)[/tex] خواهد بود.
ولی روشی که خودتون گفتید:
پیدا کردن مینیمم که [tex]O(n)[/tex] طول میکشه چرا که ممکنه درختمون اریب باشه.Tree-Successor هم همانطور که گفتید از مرتبه [tex]O(lgn)[/tex] هست.ولی الگوریتم مورد نظر خیلی پیچیده‌تر از اینه که شما به این سادگی بهش نگاه کردید و اثبات طولانی دارد.فقط همین رو بگم که ثابت میشه که هر یال درخت در این الگوریتم حداکثر دو بار پیمایش خواهد شد.