# Thread: Newbie binary tree confusion

1. ## Newbie binary tree confusion

I'm just learning about binary trees in my C text, specifically the part about deleting nodes with two children. In the example code it gives, the left side of the deleted node is attached to the parent of the deleted node, then the right side of that subtree is traversed in order to find a spot to reattach the right side of the deleted node.

Does it matter which side of the deleted node is reattached to the parent? The text uses a deletion of a node which is attached to the left side of its parent as an example and the example code follows from this. But I presume that this code also applies to the case in which the deleted node is attached to the right side of its parent. In other words, does it matter what physical "shape" your tree ends up in (its imaginary shape anyway), as long as it's technically correctly ordered, i.e. everything on the correct side of everything else?

I guess I was expecting the side of initial reattachment to depend on whether the deleted node was attached to the right or left of its parent, and was surprised to see that the code given picked one way of doing it over the other for both cases.

2. Some code might pick between the next greatest or next smallest at random, but yes most implementations just always go one way.
It simply doesn't matter which you choose though. The only time you ever care about the tree shape upon deletion is when you're using a type of self-balancing binary tree. Even then though, the shape upon deletion is taken care of by other means.
If you're using an ordinary binary tree then the effect of deletions on performance is the least of your worries.

3. Originally Posted by iMalc
Some code might pick between the next greatest or next smallest at random, but yes most implementations just always go one way.
It simply doesn't matter which you choose though. The only time you ever care about the tree shape upon deletion is when you're using a type of self-balancing binary tree. Even then though, the shape upon deletion is taken care of by other means.
If you're using an ordinary binary tree then the effect of deletions on performance is the least of your worries.
Thanks, that's cleared things up for me.