אין הקדמה נפרדת לשאלה זו — הנוסח המלא של השאלה מופיע בסעיף א'.

public static bool IsSmaller(Queue<int>q1, Queue<int> q2)

כתבו פעולה המקבלת שני תורים של מספרים שלמים q1-ו q2. הפעולה תבדוק אם כל הערכים של תור q1 קטנים מכל הערכים של תור q2. אם כן, הפעולה תחזיר ערך true, ואם לא – הפעולה תחזיר ערך false.

public static bool IsUpTree(BinNode<Queue<int>> root)

נתון עץ שבו כל צומת מכיל תור של מספרים שלמים. עץ נקרא "עץ מעולה" אם הוא עונה על שני התנאים האלה: (1) לכל צומת שאינו עלה יש שני בנים. (2) כל הערכים הנמצאים בצומת האב גדולים מכל הערכים הנמצאים בבן השמאלי וקטנים מכל הערכים הנמצאים בבן הימני. כתבו פעולה המקבלת עץ בינארי של תורים שלמים ובודקת אם העץ הוא "עץ מעולה".

לדוגמה, העץ שלפניכם הוא "עץ מעולה":

• השורש: תור [12, 10, 7]
• הבן השמאלי של השורש: תור [4, 6, 2, 3] — עלה
• הבן הימני של השורש: תור [20, 25, 43], ולו שני בנים:
  • בן שמאלי: תור [13, 18, 16] — עלה
  • בן ימני: תור [48, 50, 66] — עלה

נתונה טענה: ערך הכי קטן ב"עץ מעולה" נמצא בעלה הכי שמאלי. האם הטענה נכונה? הסבירו את תשובתכם.

מהי סיבוכיות של הפעולות שכתבתם? הסבירו את תשובתכם.