(5 pts – 1 pt/number) Given the following sequence of numbers: 8, 0, -68, 3, 13,

Question

(5 pts – 1 pt/number) Given the following sequence of numbers: 8, 0, -68, 3, 13, 10. If the numbers are inserted into a BST in the sequence provided, then what would the tree look like? Draw a diagram for the BST. Be sure to show both branches of a given node.

(6 pts) Using the BST constructed in question (2), answer the following questions:

i. (2 pts) How many comparisons are required to find the number 3?        ________     ii. (2 pts) How many children does the node containing the number 0 have? ________

iii.(2 pts) The tree may consist of multiple leaf nodes. Provide the number in the leaf node stored in the rightmost subtree.   ________            

Explanation / Answer

The Binary search tree is constructed as follows,

Step1 : 8

Step 2:

8
/   
   0

Step 3:

8
/   
   0
/
-63

Step 4:

   8
/   
   0
/
-63 3

Step 5:

8
/
   0 13
/
-63 3

Step 6:

8
/
   0 13
/ /
-63 3 10

Answers:

i. Based on the tree, it will take three comparisons to find the number 3

ii. There are two children for the number 0

iii. The number 10 is stored in the rightmost subtree

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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