Question

Draw a binary decision tree for searching a four-element ordered list by sequantial search. (explain each step in thorough detail.)

Answer 1

Solution:

This is a very straightforward question. Use the obvious observation that sequential search in a sorted array can be stopped as soon as an element larger than the search key is encountered.

You can go also with the second different decision tree.

For this idea, you just made the right skewed tree so that the sorted list could be easily traversed sequentially.

As given list contains sorted element, and we have to search an element among them, so just by traversing the following tree,

check

if required element == A[0] then go to left side and terminate.

else check required element == A[1] then go to its left side and terminate.

else check required element == A[2] then go to its left side and terminate.

else check required element == A[3] then go to its left side and terminate.

else element is not found in the list.

By following this, we can construct decision tree as follows:

Please give thumbsup, if you like it. Thanks.