# Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8

Question:

Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8 (in that order) into an (initially) empty binary search tree. Show also the intermediate tree after the first five integers are inserted. Next, show the trees resulting from first deleting 4 and then 10.

So, I'm not entirely sure if i'm even doing this right, I also am not entirely sure the process of what a tree might look like when deleting specific nodes. Here is what I have so far:

Where: $a)$ = Tree after first 5 integers are inserted, $b)$ = B.S.T after inserting all integers, and $c)=$ B.S.T. resulting from first deleting 4, then 10.

$a)$

$b)$

$c)$ Not really sure what takes place here... When I delete the node containing 4, does the B.S.T. then move up the node containing 2 to be a child of the node containing 9? Also if I delete the node containing 10, which node becomes the root? Also isn't it true that everything descending to the left of the root must be less than the root and everything descending to the right of the root must be greater than the root?

• The two cases you mention are pretty straight forward but it can be more complicated. Take a look at algolist.net/Data_structures/Binary_search_tree/Removal – John Douma Nov 7 '15 at 20:28
• I see, working that out now.. So does my a) and b) look correct? I made some revisions. – Shammy Nov 7 '15 at 20:56
• Yes. Your trees look correct. – John Douma Nov 7 '15 at 21:07
• @JohnDouma Can you check my solution when you get a chance, I added an answer. – Shammy Nov 15 '15 at 20:39

## 1 Answer

So would it be correct for me to go to the lowest node in the lowest level subtree to the left (i.e. 5) and then use that node to overwrite the node I'm trying to delete? So essentially I overwrote the node I wanted to delete 4 with 5 then deleted node 5 and thus: $c_1 =$ B.S.T. after deleting 4 and $c_2 =$ B.S.T. after deleting 10

so:

$c_1$:

and then for deleting 10 I find the smallest node in the right tree which is 11 and I overwrite 10 with that and then delete 11 so:

$c_2:$