sathi23
BAN USERConsidering the fact that the tree has a left pointer, right pointer and another extra pointer say 'next' which would help the leaf nodes to be linked and form a linked list. I guess this works fine for all the cases. Do check.
The node returned will be the head of the list. Traverse the tree in preorder and collect the leaf nodes and link them.
struct node* returnlisthead(struct node* headref)
{
struct node* left;
struct node* right;
if(headref==NULL)
return NULL;
else if(headref->left==NULL && headref->right==NULL)
return headref;
else
{
left= returnlisthead(headref->left);
right=returnlisthead(headref->right);
if(left!=NULL)
left->next=right;
}
if(left!=NULL)
return left;
else
return right;
}
@ hopebasedcoder: ur solution might just test whether the sorting alone is done properly. I dont see the need of the pointer given for the unsorted linked list. May be the person should have asked the interviewer like, do we also need to test whether all the elements in the sorted linked list are the ones present in the given input. Is that a check to be done? Since its a question for a sdet, I guess we should test the output from all angles
- sathi23 May 04, 2009