Kingdom of Saudi Arabia اﻟﻤﻤﻠﻜﺔ اﻟﻌـﺮﺑﯿﺔ اﻟﺴﻌﻮدﯾﺔ
Ministry of Higher Education وزارة اﻟﺘﻌﻠﯿﻢ اﻟﻌﺎﻟﻲ
Prince Sattam bin Abdulaziz University ﺟﺎﻣﻌﺔ اﻷﻣﯿﺮ ﺳﻄﺎم ﺑﻦ ﻋﺒﺪاﻟﻌﺰﯾﺰ
College of Computer Engineering and Sciences ﻛﻠﯿﺔ ھﻨﺪﺳﺔ وﻋﻠﻮم اﻟﺤﺎﺳﺐ
Computer Science Department ﻗﺴﻢ ﻋﻠﻮم اﻟﺤﺎﺳﺐ
Course Title: Data Structures and Algorithms (CS2321) / 1437-1438 (2)
Homework 4 (Solutions)
(1) (a) A.
(b) G, H, I, L, M, and K.
(2) For node B:
(a) A.
(b) D and E.
(c) C.
(d) 1.
(e) 3.
(3) 4.
(4) Proof is by induction. The theorem is trivially true for h = 0. Assume true for h = 1,2, . . . ,k. A tree of height k + 1 can
have two subtrees of height at most k. These can have at most 2k + 1-1 nodes each by the induction hypothesis. These
2k + 2-2 nodes plus the root prove the theorem for height k + 1 and hence for all heights.
(5) (a) - * * a b + c d e.
(b) ( ( a * b ) * ( c + d ) ) - e.
(c) a b * c d + * e -.
(6)
CS2321 – Homework 4 Page 1/7
, (7)
(8)
Algorithm find(x,*t)
Input: x is the value to find, t a reference on the root of a subtree.
Output: the reference of the node containing x or NULL if x doesn’t exist in the tree.
1. if (t==NULL)
2. return NULL;
3. else if (x < t->key)
4. return find(x,left(t));
5. else if (x > t->key)
6. return find(x,right(t));
7. else
8. return t;
CS2321 – Homework 4 Page 2/7
Ministry of Higher Education وزارة اﻟﺘﻌﻠﯿﻢ اﻟﻌﺎﻟﻲ
Prince Sattam bin Abdulaziz University ﺟﺎﻣﻌﺔ اﻷﻣﯿﺮ ﺳﻄﺎم ﺑﻦ ﻋﺒﺪاﻟﻌﺰﯾﺰ
College of Computer Engineering and Sciences ﻛﻠﯿﺔ ھﻨﺪﺳﺔ وﻋﻠﻮم اﻟﺤﺎﺳﺐ
Computer Science Department ﻗﺴﻢ ﻋﻠﻮم اﻟﺤﺎﺳﺐ
Course Title: Data Structures and Algorithms (CS2321) / 1437-1438 (2)
Homework 4 (Solutions)
(1) (a) A.
(b) G, H, I, L, M, and K.
(2) For node B:
(a) A.
(b) D and E.
(c) C.
(d) 1.
(e) 3.
(3) 4.
(4) Proof is by induction. The theorem is trivially true for h = 0. Assume true for h = 1,2, . . . ,k. A tree of height k + 1 can
have two subtrees of height at most k. These can have at most 2k + 1-1 nodes each by the induction hypothesis. These
2k + 2-2 nodes plus the root prove the theorem for height k + 1 and hence for all heights.
(5) (a) - * * a b + c d e.
(b) ( ( a * b ) * ( c + d ) ) - e.
(c) a b * c d + * e -.
(6)
CS2321 – Homework 4 Page 1/7
, (7)
(8)
Algorithm find(x,*t)
Input: x is the value to find, t a reference on the root of a subtree.
Output: the reference of the node containing x or NULL if x doesn’t exist in the tree.
1. if (t==NULL)
2. return NULL;
3. else if (x < t->key)
4. return find(x,left(t));
5. else if (x > t->key)
6. return find(x,right(t));
7. else
8. return t;
CS2321 – Homework 4 Page 2/7
