‫حذف غیر بازگشتی یک درخت دودویی در فضای ثابت: بازسازی درخت

در این مقاله، روشی برای حذف غیر بازگشتی گره‌های یک درخت دودویی در فضای ثابت ارائه شده است. الگوریتم با چرخاندن درخت به صورت 45 درجه و پیوند زدن زیردرخت راست به انتهای زنجیره چپ آغاز می‌شود. سپس گره ریشه حذف شده و زیردرخت چپ به عنوان ریشه جدید در نظر گرفته می‌شود. این فرآیند تا زمانی که تمام گره‌ها حذف شوند تکرار می‌شود. الگوریتم با پیچیدگی زمانی O(n) کار می‌کند و ترتیب حذف عناصر شبیه به preorder است، اگرچه به دلیل عدم حذف فوری زیردرخت راست پس از زیردرخت چپ، یک preorder واقعی نیست. این روش به دلیل کوتاهی و سهولت در درستی، ترجیح داده می‌شود.