To complete our discussion of Binary Search Trees we need to discuss the bstDelete operation. The process would go something like the following:<p>

</p><pre>Search for a node containing the "key" value<br><br>if (key not found)<br>  return<br>else if (either subtree is empty)<br>{<br>  delete the node replacing the parents link with the <br>    ptr to the nonempty subtree or NULL if both <br>    subtrees are empty<br>}<br>else<br>{<br>  Traverse the left subtree of the node to be deleted<br>    such that you find the rightmost node (Rnode) in the left<br>    subtree<br><br>  Move the content of Rnode to the node to be deleted<br><br>  Set Rnode's parent pointer to point to the left subtree<br>    of Rnode<br><br>  Free the storage from the unused node<br>}<br></pre>

Let's take a look at the following BST:<br><br><span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 10<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 5&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 15<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2&nbsp;&nbsp;&nbsp;&nbsp; 8&nbsp;&nbsp;&nbsp;&nbsp; 12&nbsp;&nbsp;&nbsp;&nbsp; 16<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 7&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 14<br></span><p>P#1: Assume that you always start with the above tree, how would each of the following nodes be deleted?</p><p>8</p><p>12</p><p>5</p><p>15</p><p>10<br></p><p><br>P#2: How would you change the existing BT ADT to make deletion of a node in a BST easier?<br></p><p>

    
</p>