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

$T(n) = T(k) T(n – k – ۱) c$

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

$T(n) = T(0) T(n – ۱) c$

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

$T(n) = (n-1)T(0) T(1) (n-1)c$

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

$T(n) = 2T(\left \lfloor \frac{n}2 \right \rfloor ) c$

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