Bharg Bharg - 19 days ago 7
C++ Question

AVL Tree insertion - Segmentation fault

I am trying to solve this problem on Hackerrank ( https://www.hackerrank.com/challenges/self-balancing-tree ) using their editor. The following are C++ function code I wrote:

node* makeNewNode (int data)
{
node* temp= new node();
temp->val=data;
temp->left=NULL;
temp->right=NULL;
temp->ht=0;
return temp;
}

//------------------------------------------------------------
int height(node* temp)
{
if(temp==NULL)
return -1;
return temp->ht;
}

//------------------------------------------------------------
int balanceFactor(node* root)
{
if(root==NULL)
return 0;
return height(root->left)-height(root->right);
}

//------------------------------------------------------------
node* rightrotation(node* root)
{
node* temp1 = root->left;
node* temp = temp1->right;
temp1->right = root;
root->left = temp;
root->ht = max(height(root->left), height(root->right)) + 1;
temp1->ht = max(height(temp1->left), height(temp1->right)) + 1;
return temp1;
}

//------------------------------------------------------------
node* leftrotation(node* root)
{
node* temp = root->right;
node* temp1 = temp->left;
temp->left = root;
root->right = temp1;
root->ht = max(height(root->left), height(root->right)) + 1;
temp->ht = max(height(temp->left), height(temp->right)) + 1;
return temp;
}

//------------------------------------------------------------
node* insert( node* root, int data)
{
if(root == NULL)
return makeNewNode(data);

if(data<root->val)
root->left = insert(root->left, data);
else if(data>root->val)
root->right = insert(root->right, data);
else
return root;

root->ht = 1 + max(height(root->left), height(root->right));
int balance = balanceFactor(root);

if(data<root->left->val && balance>1)
return rightrotation(root);

if(data>root->right->val && balance<-1)
return leftrotation(root);

if(balance>1 && data > root->left->val)
{
root->left = leftrotation(root->left);
return rightrotation(root);
}

if(balance<-1 && data < root->right->val)
{
root->right = rightrotation(root->right);
return leftrotation(root);
}

return root;
}


I am getting Segmentation fault in the line
if(balance>1 && data > root->left->val)
but I can't figure out why. I tried putting a check for
root->left
is
null
before getting into this, but even that is giving seg fault.

Because I am using Hackerrank inbuilt editor, the main function is taken care of.

Nevertheless, for debugging purposes, I added the following main():

int main()
{
node* root=NULL;
root=insert(root,1);
root=insert(root,2);
root=insert(root,3);
return 0;
}


I tried an online gdb (www.onlinegdb.com) and it shows

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400aa2 in insert (root=0x603010, data=2) at main.cpp:86
86 if(data<root->left->val && balance>1)


Please help.

Answer

You cannot write

if(data<root->left->val && balance>1)

if root or if root->left can be nullptr.

If your AVL Tree has only a root and if you are inserting on the right node, then root->left == nullptr and root->right is your inserted node.

So the execution will go on data < root->left->val and it will generate a segmentation fault. You need to insert more conditions like

if(root->left != nullptr && data<root->left->val && balance>1)

Here is the modified insert function:

node* insert( node* root, int data)
{
    ...
    int balance = balanceFactor(root);

    if(root->left && data<root->left->val && balance>1) // here was the segmentation fault with gdb
        return rightrotation(root);

    if(root->right && data>root->right->val && balance<-1)
        return leftrotation(root);

    if(balance>1 && root->left && data > root->left->val)
    { ... }

    if(balance<-1 && root->right && data < root->right->val)
    { ... }

    return root;
}