converting a binary search tree to doubly linked list

akash picture akash · Jul 16, 2012 · Viewed 17.9k times · Source

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?

Answer

vagrawal13 picture vagrawal13 · Jul 17, 2012

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;
    }