נתונים שני מערכים \(A[1, ..., n]\) ו-\(B[1, ..., n]\). ידוע כי המערך \(A\) הוא הפלט של סריקה סופית (post-order) והמערך \(B\) הוא הפלט של סריקה תוכית (in-order) של עץ בינארי \(T\) (לאו דווקא עץ חיפוש בינארי) שכל המפתחות בו שונים זה מזה.

א. כִּתְבוּ אלגוריתם הבונה את העץ \(T\) בהינתן המערכים \(A, B\). נתחו את סיבוכיות זמן הריצה של האלגוריתם שהצעתם.

ב. האם ניתן לבנות את \(T\) מתוך \(B\) בלבד? הוכיחו את קביעתכם.