This question was asked in a recent coding interview.
Q : Given a binary tree, write a program to convert it to a doubly linked list. The nodes in the doubly linked list are arranged in a sequence formed by a zig-zag level order traversal
My approach
i could always do the zig-zag level order traversal of the tree and store it in an array an then make a double linked list. but the question demands for a in-place solution. can anyone help in explaining the recursive approach should be used?
This is the recursive approach.Note that ,here root will point to some inbetween element of the list formed. So,just traverse from root backwards to get the head.
#define NODEPTR struct node*
NODEPTR convert_to_ll(NODEPTR root){
if(root->left == NULL && root->right == NULL)
return root;
NODEPTR temp = NULL;
if(root->left != NULL){
temp = convert_to_ll(root->left);
while(temp->right != NULL)
temp = temp->right;
temp->right = root;
root->left = temp;
}
if(root->right != NULL){
temp = convert_to_ll(root->right);
while(temp->left != NULL)
temp = temp->left;
temp->left = root;
root->right = temp;
}
return root;
}