CareerCup

hi

Do breadth first traversal and keep on storing the children in next and next->next and update the prev pointers.
Problem here is we will use a queue to BFT, it may not be accepted.

This can be done in inorder traversal , without any need for additional queue.

Here is the code to convert a binary tree to a single link list. Now in order to convert it to a doubly linklist we simply need to scan it once and assign prev pointers....


void main()
{
tree_node * temp = root;
while(temp->left)
temp=temp->left;
convert_to_linklist(root);
root = temp;
//siblinglink(root);

while(root->right)
{

printf("value is %d\n", root->val);
root = root->right;
}
printf("value is %d\n", root->val);
}
void convert_to_linklist(tree_node * root)
{
if(!root)
return;
tree_node * temp = root->left;
if(temp)
{
while(temp->right)
temp = temp->right;
temp->right = root;
temp = root->left;
root->left = NULL;
convert_to_linklist(temp);

}

temp = root->right;
if(temp)
{
while(temp->left)
temp = temp->left;
tree_node * te = root->right;
root->right = temp;
convert_to_linklist(te);

}
}