middle node deletion in binary trees

[rithish]

hello im trying to delete a middle node in binary tree .but i have tried it in a linked list but here how to do that does any one them has links or video tutorials???????????

[Adak]

You googled for "node deletion in binary trees in C", and received NO hits?

Without code, I have no idea of why your logic isn't working.

[Gonbe]

I believe you made a topic about binary trees before and your case was a binary search tree right? (for everynode the condition holds that every node in it's left subtree is smaller than the node's value and every node in the right subtree is bigger or equal)

You should be able to figure out how to do this. Do it without thinking in code first, do it on paper. You could even draw an example tree if it helps you.

You will want to maintain the property mentioned earlier. For example, say you have this tree:

       8
     /   \ 
    3     10
   / \     \
  1   6     14
     / \    /
    4   7  13

And we delete the node with value 3. The tree would transform as follows:

      8
    /   \
   4     10
  / \     \
 1   6     14
      \    /
       7  13

I'll leave up to you to figure out what happened and more importantly why it happened.

[deceptikon]

Click me.

[rithish]

ok gonbe u deleted the element 3 and replaced the last left leaf node in tree am i right?????if u delete right subtree??

[Gonbe]

I am not exactly sure what you mean but if I interpret it correctly you are right:

When deleting a node from a tree you basically replace it with the most-left node from it's right subtree. And why is that? Well per definition every node in the right subtree is bigger or equal than the node you want to delete and everything to the left is smaller. This goes for every node. So the most left node in the right subtree will always be the smallest value in that subtree (Another way of putting it is to say that every other node in the right subtree is bigger or equal to this one!) but it's still bigger or equal than the node you want to delete. This means every node in the left subtree is still smaller so the rules stand.

Note that this is just the way to do it when a node has 2 subtree's. With 0 or 1 subtree deleting a node is easy.