CODEWITHSUNDEEP
c++cdata-structures
Zzz
Zzz

Reputation: 3025

Binary Search Tree - Access Violation

This method finds the largest node in a BST returns its value and deletes it. I am getting an access violation at prev->rightLink = cur->leftLink;. I am relatively unfamiliar with C++ and not able to find the cause.

int CTree::popLargest(TreeNode* tr)
{   
    int largest;
    TreeNode* prev = NULL;
    TreeNode* cur = tr;

    while (cur->rightLink != NULL)
    {
        prev = cur;
        cur = cur->rightLink;
        largest = cur->info;
        //DeleteAttemptTwo(tr, largest);//DeleteItem(largest);     
    }

    if (cur->leftLink != NULL)
    {
        prev->rightLink = cur->leftLink;
    }
    else 
    {
        prev->rightLink = NULL;
    }

    return largest;
}

Upvotes: 0

Views: 139

Answers (4)

newhand_liu
newhand_liu

Reputation: 21

The cause is that prev is still NULL. You should verify if a pointer is NULL when you dereference it.BTW, this question is easy to find by debugging.

const int INVALID_VALUE = -1;    // change it by yourself.
int CTree::popLargest(TreeNode* tr)
{  
    int largest = INVALID_VALUE;
    if (tr != NULL)
    {
        TreeNode* prev = NULL;
        TreeNode* cur = tr;
        while (cur->rightLink != NULL)
        {
            prev = cur;
            cur = cur->rightLink;
            largest = cur->info;
            //DeleteAttemptTwo(tr, largest);//DeleteItem(largest);     
        }
        if (prev != NULL)
        {
            if (cur->leftLink != NULL)
            {
                prev->rightLink = cur->leftLink;
            }
            else 
            {
                prev->rightLink = NULL;
            }
        }
    }
    return largest;
}

Upvotes: 1

Skandh
Skandh

Reputation: 426

In case when tree wouldn't have any right child, prev will remain null and while executing

prev->rightLink = cur->leftLink;

you are trying to access property of null variable, hence 'Access Voilation'.

Upvotes: 1

Vinayak Garg
Vinayak Garg

Reputation: 6606

This if and else makes little sense - 

if (cur->leftLink != NULL)
{
    prev->rightLink = cur->leftLink;
}
else 
{
    prev->rightLink = NULL;
}

What you are trying to do can be done just by - prev->rightLink = cur->leftLink;

And the reason you are getting access violation on this statement is that prev is not pointing to a valid node, which is when it is NULL (as initialized).

Upvotes: 2

AusCBloke
AusCBloke

Reputation: 18492

You're not taking into account the case where tr has no right elements (tr->rightLink = NULL, cur = tr), and therefore the contents of the while loop never execute. In that case, prev remains as NULL, which means you're then trying to dereference NULL when trying to access the rightLink element of prev.

Trying to dereference NULL will lead to some sort of access violation error.

Upvotes: 0

Related Questions