//whoever you are helping me get through this.. thank you. e. Given the followin

Question

//whoever you are helping me get through this.. thank you.

e. Given the following algorithm for deleting a a node from a binary tree (or a portion of the algorithm) in real code, be able to fill in the blanks / Define a structure to be used as the tree node struct TreeNode int // Other fields defined here TreeNode «left; TreeNode *right; Key; // This function returns true if the node was successfully deleted bool MyTree::Delete (int Key) // Create pointers for the search and delete TreeNode *back = NULL ; TreeNode *temp = root; TreeNode *delParent;// Parent of node to delete TreeNode *delNode; // Node to delete // Search for the node to delete while(( ; // Advance back pointer back - // Advance temp pointer if(Key Key) temp else temp = if( // Check to see if the one to delete was NOT found return false,;

Explanation / Answer

Hi,
I will fill the blanks in the order they appear from top to bottom.
1. First the while loop needs to iterate till the root or the back is not null
therefore it is while(temp!=NULL && back!=NULL)
2. setting back pointer to the loop variant
back=temp;
3.if its less than key then move left i.e temp=temp->left
4. if its more than key then move right i.e temp=temp->right
5.check if key is not found i.e if(temp==NULL)
6.case1 :in this case, there is no right child and hence it is if(delNode->right==NULL)
7.checking if we are going to delete root i.e if(delParent==root)
8.deleting the root here, hence root==NULL, delete delNode;
9.else case is where we are not deleting null, hence
delParent->left=delNode->left
else
delParent->right=delNode->right
10.case2: if there is a right child, i.e to check if node has left child if(delNode->left!=NULL)
11. now this is again same as parts 7-8 i.e
if(delParent==root)
root=NULL;
delete delNode;
return true;
12.again this is same as 9 i.e
delParent->left=delNode->left
else
delParent->right=delNode->right
13.CASE3: deleting node with both children
temp=delNode->left
back=delNode;
14. looping to find largest key in left subtree, hence
while(temp!=NULL)
{
back=temp;
temp=temp->left;

}
15.checking where the node to delete exists to the left or right, hence
if(back==delNode->left)
back->left=temp->left
else()
back->right=temp->right

Thumbs up if this was helpful , otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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