🚀 go-pugleaf

In <4hvfiu$h0v$1@mhadf.production.compuserve.com> Neil Ford <100717.3246@CompuServe.COM> writes:

>Hello,

>Can anyone help with a program which is required to remove a node 
>from a binary tree while maintaining its integrity.

I'm assuming you mean a plain binary tree.

There are three cases to consider.  
Case 1:  The node you want to delete has no children.
  Solution is trivial.
Case 2:  The node you want to delete has one child.
  Solution:  Remove the node and attach the child to the deleted node's 
parent, not necessarily in that order.
Case 3:  Node has two children.
  Solution:  Turn it into a Case1  or Case 2 situation by using a method 
called the Inorder Successor Method.  Swap the **contents** (in this case 
a pointer to a linked list), with the contents of the node's inorder 
successor (the next highest value).  The inorder successor can never have 
more than one child, leaving you with a Case 1 or Case 2 situation.  The 
inorder successor is physically located to the right one node and down as 
far left as you can go.

-- 

  Tim Groner
  e-mail: Tim_Groner@Umanitoba.ca
  http://home.cc.umanitoba.ca/~umgroner