שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2021 - עצים בינאריים

אם שני צמתים בעץ לא נמצאים באותה רמה בעץ, ואף אחד מהם אינו השורש, אז בכל סריקה הצומת השמאלי יותר ייסרק לפני הצומת הימני. נכון או לא-נכון?

רמז: חשבו על סריקת Post Order - האם תמיד צומת שמאלי ייסרק לפני ימני גם כשהם ברמות שונות?

פתרון: **נכון.** בכל שלוש סריקות העץ (Pre Order, In Order, Post Order), אם צומת A נמצא בתת-עץ השמאלי של צומת משותף כלשהו ביחס לצומת B שנמצא בתת-עץ הימני, אז A תמיד ייסרק לפני B. זה נכון ללא תלות ברמות שלהם בעץ, כי בכל הסריקות תת-העץ השמאלי נסרק **לפני** תת-העץ הימני. הטענה מציינת שהם לא באותה רמה ואף אחד אינו שורש, אך הנקודה המכרעת היא שבכל סריקה צמתים שמאליים נסרקים לפני ימניים.