درخت جست‌وجوی دودویی یک درخت ریشه‌دار $n$ رأسی با ویژگی‌های زیر است:

• رأس‌ها با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند.
• هر رأس حداکثر دو فرزند دارد که یکی ریشه‌ی زیردرخت سمت چپ و دیگری، ریشه‌ی زیردرخت سمت راست است.
• به ازای هر رأس، شماره‌های تمام رأس‌های زیردرخت سمت چپ آن (در صورت وجود) از شماره‌ی خودش کوچک‌تر و شماره‌ی تمام رأس‌های زیردرخت سمت راست آن (در صورت وجود) از شماره‌ی خودش بزرگ‌‌تر است.

برای مثال، یک درخت جست‌وجوی دودویی در زیر کشیده‌ایم:

درخت زیر را در نظر بگیرید. در هر مرحله می‌توانیم یک یال در نظر گرفته و شماره‌ی دو رأس آن را جابه‌جا کنیم. کمینه‌ی تعداد مراحل لازم را بیابید، طوری که بتوانیم شکل را به یک درخت جست‌وجوی دودویی تبدیل کنیم.

1. 5
2. 6
3. 7
4. 8
5. 9

• سوال قبل
• سوال بعد