Deleting a node from a search binary tree

Question

So I was studying data structures and I finally get to start to understanding binary trees. The resource that I'm using and some others articles establish some rules for removing a node from a search binary tree, and they are:

• If the node to be removed is a leaf node, just point its parent node's left/right (depending on parent's value and its child's value) to null.
• Else if the node has only its left side pointed to some node, do the parent's node points to the child's left node. Then: the "side" where the left node will be will depends on its value and parent's value, right? For example, if we want to remove 25 that has 60 on its right side and that is child from 50, should 60 be on 50's right side, correct?
• Basically, the same applies for having only right side and not left side.
• There is the possibility of the node to be deleted having two child nodes too, but I think I did understand here.

I made a very basic image on paint to what I'm trying to understand. Well, looks like I'm the only that is not understanding this, so I think I have lost some concept or anything.

Answer 1

Your example search tree is not a search tree. Because you go right from 50 and get to numbers that can be both smaller than (eg 45) and bigger than (eg 65) 50.

After you fix that, there are three cases of note.

1. The removed node is a leaf, delete it.
2. The removed node only has one branch. Replace where it went with that branch.
3. You need to merge the branches into a new tree, the root of whom goes where the deleted node was.

Complicating this in practice is the fact that we don't want trees to become unbalanced. Because unbalanced trees are not efficient to search. So sometimes you want to not simply attach, but also to rotate the tree around to get a better balanced result.

https://stackoverflow.com/a/75453554/585411 has the last time I wrote tree code. It does all of that. Perhaps studying that code will help you figure this out?