درخت دودویی فرزند-چپ همزاد-راست
درخت دودویی فرزند چپ همزاد راست چیست؟

در یک درخت باینری مانند  T می‌توان هر رأس را با دو اشاره گر در نظر گرفت. ابتدا در این درخت ریشه را تعریف می‌کنیم. سپس برای هر رأس از درخت  T یک اشاره‌گر به اولین فرزند که به آن فرزند چپ می‌گوییم و اشاره‌گر دوم را به اولین همزاد بعد از خود در درخت که به اصطلاح همزاد راست گفته می‌شود تعریف می‌کنیم. حال برای پیدا کردن فرزند  n ام یک رأس (برای مثال رأس  V) با توجه به در اختیار داشتن فرزند چپ که اولین فرزند  V است و در اختیار داشتن همزاد راست هر رأس (که در اینجا همزاد راست هر فرزند  V مد نظر است) می‌توان با پیمایش فرزندان  V فرزند  n این رأس را پیدا کرد:
procedure kth-child(V, n):
    child ← V.child
    while n ≠ 0 and child ≠ nil:
        child ← child.next-sibling
        n ← n − 1
    return child
که کد این پیمایش در زبان پایتون به قرار زیر است:
def kth-child(V, n):
    child = V.child
    while n != 0 and child is not None:
        child = child.nex-sibling
        n -= 1
    return child
در شکل روبرو در هر مرحله (الگوریتم از ریشه شروع می‌شود) فرزند چپ و یال واصل به پدر به رنگ سبز و همزادهای آن همگی به رنگ زرد در می‌آیند. حال هر یالی که به رنگ زرد است حذف می‌شود و جایگزین آن به فرزند چپ پدر متصل می‌شوند. در انتها نیز درخت به لحاظ ظاهری مرتب می‌شود.
کد الگوریتم بالا را می‌توان به زبان جاوا به شکل زیر نوشت:
public Child kth-child(V, n){
    Child Child = V.Child ;
    while(n != 0 && child != null){
        Child = Child.nex-sibling ;
        n -- ;
    }
    return child ;
}
که تنها باید به این نکته توجه کرد که در صورت وجود  n امین فرزند  V برنامه به عنوان خروجی آن را بازگردانی می‌کند و در غیر این صورت خروجی تهی خواهد بود.
پروسه تبدیل یک درخت  K تایی به یک درخت دودویی فرزند چپ همزاد راست گاهی با نام تبدیل کنوت (به انگلیسی: Knuth transform) شناخته می‌شود.
می‌توان الگوریتمی به قرار زیر ارائه داد تا با استفاده از آن بتوانیم یک درخت  K تایی را به یک درخت دودویی فرزند چپ همزاد راست تبدیل کنیم. در این الگوریتم ابتدا ریشه درخت   K تایی را به عنوان ریشه این درخت نیز انتخاب می‌کنیم. حال برای هر رأس در درخت دودویی فرزند چپ همزاد راست مانند  E فرزند چپ در درخت  K تایی را فرزند چپ و همزاد راست در درخت  K تایی را فرزند راست در این درخت قرار می‌دهیم.
حال می‌خواهیم این الگوریتم را در فرایند تبدیل یک درخت به یک درخت دودویی فرزند چپ همزاد راست بررسی کنیم و در این الگوریتم در شکل اول درخت باینری را مشاهده می‌کنیم که قرار است الگوریتم بر روی آن اجرا شود. هر رأس در این الگوریتم دارای دو نشانه گر است که با استفاده از آن‌ها یال‌ها در درخت نهایی رسم خواهند شد که آن دو نشانه گر فرزند چپ. همزاد راست رأس هستند.
۱
                                                                                 /|\
                                                                                / | \
                                                                               /  |  \
                                                                              ۲   ۳   ۴
                                                                             / \      |
                                                                            ۵   ۶     ۷
                                                                                     / \
                                                                                    ۸   ۹
حال در صورتی که برای هر رأس تنها دو اشاره‌گر یعنی فرزند چپ یا اولین فرزند و همزاد راست یا اولین خواهر یا برادر را به یک دیگر از طریق یال وصل کنیم و باقی مانده یال‌ها را از درخت پاک کنیم خواهیم داشت:
۱
                                                                                 /
                                                                                /
                                                                               /
                                                                              ۲ ---- ۳ ---- ۴
                                                                             /             /
                                                                            ۵ ---- ۶      ۷
                                                                                         /
                                                                                        ۸ ---- ۹
که اگر دقت کنیم شکل حاصل یک درخت دودویی فرزند چپ همزاد راست خواهد بود. کافی است خط چین‌ها را که به درخت اضافه کرده‌ایم و عمودی هستند را ۴۵ درجه دوران بدهیم.
۱
                                                                                 /
                                                                                /
                                                                               /
                                                                              ۲
                                                                             / \
                                                                            /   ۳
                                                                           ۵     \
                                                                            \     \
                                                                             \     ۴
                                                                              ۶   /
                                                                                 ۷
                                                                                /
                                                                               ۸
                                                                                \
                                                                                 ۹
مثالی دیگر از این الگوریتم را می‌توانید در شکل زیر مشاهده کنید: