Almost done! C++ function to delete the given value from a binary search tree. F

Question

Almost done! C++ function to delete the given value from a binary search tree. Function takes two arguements... tree node and value of node whose right child has to be deleted, Also replace deleted node whose right child has to be deleted. All I need is the function to do this. I'm working on c++11 code::blocks

I NEED TO MATCH THIS FUNCTION TO WORK WITH THE STRUCT

Write a C++ function to delete the given value from the binary search tree. The function takes two arguments, tree node and value of the node whose right child has to be deleted. Also replace the deleted node with minimum value from its left sub tree. For example: If the key = 25, delete its right child which is 30. Then replace it with the minimum value in the left sub-tree (of 30) which is 27. The final tree is:

Explanation / Answer

void deleteAndReplaceLeftMin(struct TreeNode **root, int key) // root is taken as double pointer because no return value for function
{
    int found ;
    struct TreeNode *parent, *x, *xsucc ;

    /* if tree is empty */
if ( *root == NULL )
    {
        printf ( " Tree is empty" ) ;
        return ;
    }

    parent = x = NULL ;

    /* call to search function to find the node to be deleted */
    search ( root, key, &parent, &x, &found ) ; // starts searching parent node "root" for "key", and updates "x", "parent" nodes and "found" values

    /* if the node to deleted is not found */
if ( found == 0 ) //found is false
    {
        printf ( " Data to be deleted, not found" ) ;
        return ;
    }

    /* if the node to be deleted has two children */
if ( x -> left != NULL && x -> right != NULL )
    {
        parent = x ;
        xsucc = x -> right;

        while ( xsucc -> left != NULL )   // rotating of tree nodes
        {
            parent = xsucc ;
            xsucc = xsucc -> left ;
        }

        x -> key = xsucc ->key ;
        x = xsucc ;
    }

    /* if the node to be deleted has no child */
if ( x -> left == NULL && x -> right == NULL ) // no left and right nodes, like leaf
    {
        if ( parent -> right == x )
            parent -> right = NULL ;
        else
            parent -> left = NULL ;

        free ( x ) ;
        return ;
    }

    /* if the node to be deleted has only rightchild */
if ( x -> left == NULL && x -> right != NULL )
    {
        if ( parent -> left == x )          
            parent -> left = x -> right ; // root's left will be move to right child
        else
            parent -> right = x -> right ; // other wise root's right will be deleting x node

        free ( x ) ;   // then delete x node
        return ;
    }

    /* if the node to be deleted has only left child */
if ( x -> left!= NULL && x -> right == NULL )
    {
        if ( parent -> left == x )
            parent -> left = x -> left ;   // move root's left to found x leftchild
        else
            parent -> right = x -> left ; // otherwise root's right will be found x left

        free ( x ) ;
        return ;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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