Textbook: Introduction to algorithms 3rd edition(2009). Thomas H. Corman

Follow the TREE-DELETE procedure described in the textbook, show step-by-step output of each of the following operations applied on the binary search tree below. a) Delete node 7. b) Based on output from step a), insert node 19. c) Based on output from step b), delete node 11. d) Based on output from step c), insert node 18. e) Based on output from step d), delete node 17.

## Expert Answer

Initial tree that we have

a – delete node 7 traverse to the node containing 7-

now remove 7 and connect node with value 17 to 20

b- Insert node with value 19

its very simple we traverse fromm root till the position where 19 should be added and add the node at that position as it is a BST 19> 6 so it will be at its right not at right we have 20 so 20>19 so 19 will move to the left in left we have 17 and 17<19 so 19 will be added to its right.

c-

delete node 11

we traverse the whole tree to find the node containing the element but as there is no element with value 11 so there is no change in the tree.

D- Insert Node 18 so

we have to find the position to add node 18 so we start with root 6 as 6<18 so it will move to right in the right there is 20 as 18<20 so it will move to left of 20 in the left of 20 we have 17 and as 17<18 so 18 will move to right of 17 in the right of 17 we have 19 and as 19>18 so it will be addes to the left of node 19.

E- Delete node 17

first we find the location of 17 as the node 17 is found we delete it but we have connected nodes to 17 which we have to connet to 20 we have 9,18,19 we choose 18 to connect to the node to 20 so that tree is balanced.