Bharg - 1 year ago 72
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)
``````

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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download