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

נתונה השיטה find2 מהמחלקה BinaryTree: ```java public static Node find2(Node root, int x, int y) { if (root == null) return null; if (root.getNumber() == x || root.getNumber() == y) return root; Node ans1 = find2(root.getLeftSon(), x, y); Node ans2 = find2(root.getRightSon(), x, y); if (ans1 != null && ans2 != null) return root; if (ans1 != null) return ans1; if (ans2 != null) return ans2; return null; } ``` מה מבצעת השיטה find2 באופן כללי כשהיא מקבלת כפרמטרים: שורש של עץ בינרי root, שכל הערכים בצמתיו שונים זה מזה, ושני מספרים שלמים x ו-y? שימו לב, עליכם לתת תיאור ממצה של מה עושה השיטה באופן כללי, ולא תיאור של מה עושה כל שורה בשיטה. כלומר, לכתוב בקצרה מה משמעות הערך שהשיטה מחזירה. **התייחסו למקרי קצה.**

רמז: שימו לב מתי השיטה מחזירה את root עצמו — כשיש תוצאה חיובית משני תתי-העצים. מה המשמעות?

פתרון: השיטה **find2** מוצאת את **האב הקדמון המשותף הנמוך ביותר (LCA — Lowest Common Ancestor)** של שני צמתים עם הערכים x ו-y בעץ הבינרי. **ההיגיון**: אם x או y נמצאים בשורש — השורש הוא ה-LCA. אם x ו-y נמצאים בתתי-עצים **שונים** (אחד בשמאל ואחד בימין), השורש הנוכחי הוא ה-LCA (כי שניהם ans1 ו-ans2 אינם null). אם שניהם באותו תת-עץ, ה-LCA מוחזר מהקריאה הרקורסיבית. **מקרי קצה:** - אם x או y (או שניהם) לא קיימים בעץ, השיטה עלולה להחזיר צומת שאינו LCA אמיתי — היא מחזירה את הצומת הראשון שנמצא (x או y) גם אם השני לא קיים. - אם העץ ריק, מחזירה `null`. - אם x הוא אב-קדמון של y (או להפך), מחזירה את הצומת העליון מביניהם.