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?
Best 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:$