Question

Draw the binary search tree that results from starting with an empty tree and a. adding 50 72 96 94 26 12 11 9 2 10 25 51 16 17 95 b. adding 95 17 16 51 25 10 2 9 11 12 26 94 96 72 50 c. adding 10 72 96 94 85 78 80 9 5 3 1 15 18 37 47 d. adding 50 72 96 94 26 12 11 9 2 10, then removing 2 and 94 e. adding 50 72 96 94 26 12 11 9 2 10, then removing 50 and 26 f. adding 50 72 96 94 26 12 11 9 2 10, then removing 12 and 72
C D E F only please

Answer 1

Binary search tree is a binary tree structure where each node has value less than it to the left and values greater to it to its right.

As only E and F are required, here is the solution -

(e)

1. Add so 60 2. Add 72 to right of so (50 3. Add 96 to right of 72 150 (96 4. 94 is added to left of 96 70 (96 194 5. 26 is added lot of 50 and 12 is added left of 26

50 (96 (12 1947 Il is added left of 12 and 9 is added left of 11 50 (96 9 7. 2 is added left of a and 10 is added eight of 9 50 172 12 (94)

8. Delete 50 50 has a children (a) Find its inpoder successes Celement which comes after 50 while in order traversal In order traversal = 2,9, 10, 11, 12, 26,50,72. horder successor - 72 (b) Put 72 in place of 5o & delete 72. o copy child (96) and delete of (d) 96 has just one child = copy 94 & delite ef (c) 72 har (72) 26 196 94 9. Delete 26, 26 has 1 chold - Replace with the child

And recursively delete the children. Hence the final tree becomes -

72 12 96 94 न TO

(f)

The values inserted are the same as part e.

1. Delete 12, 12 has 1 child

Replace 12 with its child (11) and delete the child recursively.

50 72 7) 4 94 Z

2. Delete 72, 72 has 1 child

Replace 72 with its child (96) and delete 96

Replace 96 with its child 94 and delete 94 (has no child).

Hence the final tree becomes -

50 96 (4 (2- 10