search in a binary search tree (10 pts) Suppose that we are doing search in a bi

Question

search in a binary search tree

(10 pts) Suppose that we are doing search in a binary search tree. Answer the following (a) Is it possible for the search to visit the following key values (in the corresponding se- quence)? 8, 20, 15, 19, 18 You need to write either YES or NO, and provide a brief explanation supporting your answer (b) Is it possible for the search to visit the following key values (in the corresponding se- quence)? 8, 20, 25, 19, 18 You need to write either YES or NO, and provide a brief explanation supporting your answer

Explanation / Answer

a) Given sequence of search key values : 8,20,15,19,18  

ANS: YES

This given search sequence is possible.

Explanation:

In Binary Search Tree on right side of each parent node’s number should be greater than it’s value; and left side values are less than the parent node’s value. Now starting search sequence from 8 if we notice, we can observe that next search value is 20 which is greater than 8 so searching control goes to right sub tree after 8; hence it can be said that all the search keys after 20 will be greater than 8 which is true in this given case.

Now take the node value of 20; after searching 20 next search value is 15 ; 15 is less than 20 so search control goes to left sub-tree of 20 from this point; hence it can be said that all the search keys after 15 will be less than 20 which is true in this given case.

Now take the node value of 15; after searching 15 next search value is 19 ; 19 is greater than 15 so search control goes to right sub-tree of 15 from this point; hence it can be said that all the search keys after 19 will be greater than 15 which is true in this given case.

Now take the node value of 19; after searching 19 next search value is 18 ; 18 is less than 19 so search control goes to left sub-tree of 19 from this point; hence it can be said that all the search keys after 18 will be less than 19 which is true in this given case as at 18 the search sequence is over.

Next node value is 18; and it is the last search value; hence it is observed that the given search sequence is possible.

b) Given sequence of search key values : 8,20,25,19,18

ANS: NO

This given search sequence is NOT possible.

Explanation:

In Binary Search Tree on right side of each parent node’s number should be greater than it’s value; and left side values are less than the parent node’s value. Now starting search sequence from 8 if we notice, we can observe that next search value is 20 which is greater than 8 so searching control goes to right sub tree after 8; hence it can be said that all the search keys after 20 will be greater than 8 which is true in this given case.

Now take the node value of 20; after searching 20 next search value is 25 ; 25 is greater than 20 so search control goes to right sub-tree of 20 from this point; hence it can be said that all the search keys after 25 will be greater than 20 but in the given case it is not true as 19 and 18 are next search key values both of them are less than 20. So the

Hence it is observed that the given search sequence is NOT possible.

/*Hope this helps. Thanks.*/

/*If this helps you, please let me know by giving a positive thumbs up. In case you have any queries, do let me know. I will revert back to you. Thank you!!*/

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.