אפשר לפתור בO(H) זכרון נוסף H הוא גובה העץ, שזה בעץ מאוזן
יוצא log(N)

כמובן שאי אפשר בפחות מO(N) זמן.

נסרוק העץ DFS, נגלה מה עומקו, נכין מערך שלמים בגודל מתאים,
נאתחל את האיברים הזוגיים לMIN_INT ואת האי-זוגיים לMAX_INT.

נסרוק את העץ DFS בשנית, נבדוק עומק הצומת, נשווה הערך בצומת לערך
המתאים במערך, ואם הכל בסדר נקבע את ערך התא המתאים לערך הצומת
ונמשיך אחרת נעצור עם ערך שקר.
נסיים עם אמת.

הפתרון שלי:
1) סרוק את העץ DFS מצא עומק מקסימלי.
2) הקצה דינאמית מערך ARR של משתנים, שאורכו כעומק העץ.
3) אתחל את האיברים הזוגיים במערך לערך מינמלי של integer
הוא MININT, ואת האיברים האי-זוגיים לMAXINT

4) סרוק את העץ DFS בשנית, עבור כל צומת בצע:
4.1) סמן את עומק הצומת בi.
4.2) אם הצומת זוגי וערך הצומת קטן מARR[i] החזר FALSE
4.3) אם הצומת אי זוגי וערך הצומת גדול מARR[i] החזר FALSE
4.4) הצב בARR[i] את ערך הצומת.
5) החזר אמת.