The code below implements a merge for a max leftist heap. When it is run, it sto
ID: 3580225 • Letter: T
Question
The code below implements a merge for a max leftist heap. When it is run, it stops working saying you are following a null pointer. Fix the problem.
Node * LeftistHeap::merge(Node * t1, Node * t2)
{ if (t1 == NULL) return t2;
if (t2 == NULL) return t1;
Node * t;
if (t1->element.key > t2->element.key)
{
t = t1;
t1->right = merge(t1->right, t2);
}
else
{
t = t2;
t2->right = merge(t2->right, t1);
}
Node * tr = t->right;
Node * tl = t->left;
if (tl == NULL || tr == NULL) t->npl = 0;
else t->npl = min(tl->npl, tr->npl) + 1;
if (tr->npl >tl->npl) swapKids(t);
return t;
}
Explanation / Answer
Node * LeftistHeap::merge(Node * t1, Node * t2)
{ if (t1 == NULL) return t2;
if (t2 == NULL) return t1;
Node * t;
if (t1->element.key > t2->element.key)
{
t = t1;
t1->right = merge(t1->right, t2);
}
else
{
t = t2;
t2->right = merge(t2->right, t1);
}
Node * tr = t->right;
Node * tl = t->left;
if (tl == NULL || tr == NULL) t->npl = 0;
return t;
else t->npl = min(tl->npl, tr->npl) + 1;
if (tr->npl >tl->npl) swapKids(t);
return t;
}