Fill in the missing parts of the delete method of the binary tree class // -----

Question

  Fill in the missing parts of the delete method of the binary tree class     // -------------------------------------------------------------         public boolean delete(int key) // delete node with given key         {                           // (assumes non-empty list)                 Node current = root;                 Node parent = root;                 boolean isLeftChild = true;                  while(current.iData != key)        // search for node                 {                         parent = current;                         if(key < current.iData)         // go left?                         {                                 isLeftChild = true;                                 current = current.leftChild;                         }                         else                            // or go right?                         {                                 isLeftChild = false;                                 current = current.rightChild;                         }                         if(current == null)             // end of the line,                                 return false;                // didn't find it                 }  // end while                 // found node to delete                  // if no children, simply delete it                 //put your code here                    // if no right child, replace with left subtree                 //put your code here                   // if no left child, replace with right subtree                 //put your code here                   else  // two children, so replace with inorder successor                         //put your code here                             // (successor cannot have a left child)                         return true;                                // success         }  // end delete()         // ------------------------------------------------------------- 

Explanation / Answer

// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;

while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
              
// if no children, simply delete it
//put your code here
               if(current.leftChild==null && current.rightChild == null)
                   current = null;

// if no right child, replace with left subtree
//put your code here

               else if(current.leftChild == null)
                   current = current.rightChild;
// if no left child, replace with right subtree
//put your code here
               else if(current.rightChild == null)
                   current = current.leftChild;

else // two children, so replace with inorder successor
//put your code here
                       {
                           Node min = getMinNode(current.right);
                           current.rightChild = delete(min.iData);
                       }

// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
      
       Node getMinNode(Node t) {
           if (t == null) {
               return null;
           } else if (t.leftChild == null) {
               return t;
           } else {
               return getMinNode(t.leftChild);
           }
       }

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.