Tree delete JAVA Assignment | part2: delete methods & helpers | Data Structures & Algorithm Analysi

More Data Structures and Algorithm Analysis videos:
https://youtube.com/playlist?list=PLZPy7sbFuWViIs2tnMRzkr6-1Pr2I3o3o

Notes for Data Structures and Algorithm Analysis:
https://docs.google.com/document/d/1YU8wUtH0_bOHlAM1MqOAbxnZhQQBJ0yHYA-lNPafgkM/edit?usp=sharing


Tree Delete Assignment Instructions:
https://docs.google.com/document/d/1SFzNsmQ8lUsTjC7FOhUYOPJhevt4OSdNDLGyddGSHlw/edit?usp=sharing


For deleting a node that has either one child or no children, can I use the same snippet of code as below?
If (leaf.right!= null)
return leaf.right
Else
return leaf.left

A: Yes because in the case of no children, you will be returning null which would qualify for the no children. It would also qualify for the one child since the one that is not null will be returned. This would mean that in essence you have 2 conditions

Two children
One or no children

How do I deal with getting rid of a node that has 2 children
A:
go to the right child of the node that you want to delete. Recursively go to the left until you have no more left. Return the node or the value sitting in the node.

Replace the value of the last step with the value of the node that is being deleted. Keep in mind that you do not want to delete the node but rather just change its value

The last step is to go to the right of the node that has the substituted value (the node that you wanted to delete) and issue the delete function against the substituted value to get rid of the duplicate