א. כיתבו אלגוריתם המקבל כקלט סריקה תחילית של עץ-חיפוש-בינארי \(T\) הנתונה כמערך \(A\) בן \(n\) איברים (האינדקס הראשון שלו הוא 1) ומחשב את האיבר המינימלי ב-\(A\).
שימו לב: האלגוריתם צריך להיות מחושב ישירות על המערך ללא שחזור העץ. ניתן להניח שמפתחות העץ ייחודיים (ללא חזרות). יש לכתוב את השגרה היעילה ביותר האפשרית. נתחו את הסיבוכיות כפונקציה של גובה \(T\) וכן נתחו נכונות בקצרה אך באופן מדויק.

ב. התבוננו בשגרה הבאה שהקלט אליה הוא מערך \(A\) בגודל \(n\) (האינדקס הראשון שלו הוא 1):

Find(A,n)
  Initialize stack S
  For i ← 1 to n
    While S ≠ ∅ and ?
      Pop(S)
    If S = ∅
      then print A[i]
    Push(S, i)

בשורה הראשונה מאותחלת המחסנית \(S\) (כמחסנית ריקה) אשר נוסף לשגרות ה-Push ו-Pop תומכת גם בשגרות של בדיקת ריקנות המחסנית (התנאי $S e \emptyset$ מקבל ערך אמת "נכון" בדיוק כאשר המחסנית אינה ריקה) וכן בשגרה Top(S) המחזירה את האיבר בראש המחסנית (זו שאילתא שאינה משנה מידע).

1. החליפו את סימן השאלה בשורה השלישית בשגרה בתנאי מתאים כך שהשגרה תדפיס את כל האיברים ב-\(A\) שכל האיברים המופיעים לפניהם במערך קטנים או שווים להם.
2. נסחו שמורת לולאה (אין צורך להוכיחה) שבעזרתה ניתן להוכיח את הטענה שפלט האלגוריתם הוא מה שנטען בתת-סעיף הקודם.
3. נתחו את סיבוכיות השגרה בקצרה ובמדויק.