برای این سوال تو کتاب پارسه گزینه ۴ رو انتخاب کرده و کلید سنجش گزینه ۱/
به نظر من در بدترین حالت باید مسیر بین سمت راست ترین برگ و سمت چپ ترین برگ رو به دست بیاریم.
تو حل پارسه جوری نوشته انگار ما میدونیم v دقیقا کجاست و مستقیم بدون گشتن همه گره های درخت رفته سر گره v.
در حالی که در این حالت فرضا برای ۱۵ گره جواب ۲۳ به دست میاد و این جواب در هیچ گزینه ای صدق نمیکنه.
از گره u شروع می کنیم وباید تمام گره‌ها رو بگردیم تا بتونیم گره v رو پیدا کنیم.در این روش بعضی گره های میانی هم بیشتر از یک بار پیمایش میشوند.
مشکل کجاست؟
توی درخت هر کس دقیقاً یه بابا داره پس از یه راس مثلاً u شروع میکنیم، همین طوری از باباش میریم بالا (!!) تا به ریشه برسیم! و چون توی درخت بین هر دو راس دقیقاً یه مسیر وجود داره این مسیر از u تا ریشه یکتاست و توی log n پیدا میشه! برای v هم همین کار رو میکنیم. بعد توی این دو تا مسیر بالاخره یه گره مشترک پیدا میشه که مثلاً اگه اسمش رو بذاریم w دو حالت پیش میاد:
۱/ u یا v یکیشون جد اون یکی باشه: مثلاً اگه u جد v باشه اون وقت توی مسیری که داشتیم از v میرفتیم بالا u رو هم دیدیم پس به سادگی مسیر پیدا میشه
۲/ u و v توی دو تا زیر درخت متفاوت باشن: اون وقت vwu مسیر بین u و w هست
جواب هم گزینه‌ی ۴ هست!
بدترین حالت زمانی است که اولا درخت کامل ما پر باشه و بدتر از اون اینه که گره u و v هر دو در سطح آخر باشه و بدتر از اون هم اینه که یکی در زیر درخت راست و دیگری در زیر درخت چپ باشه، خوب یه الگوریتم اینه که از جستجوی دو طرفه استفاده کنیم و از هر دو گره همزمان به عقب بر گردیم تا به ریشه برسیم پس گزینه ۴ صحیح است.