converting a binary search tree to doubly linked list

Question

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 1

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

Answer 2

Simplest method. In single inorder traversal and with just O(1) space complexity we can achieve this. Keep a pointer named lastPointer and keep track of it after visiting every node. use left and right

public void toll(T n) {
    if (n != null) {
        toll(n.left);
        if(lastPointer==null){
            lastPointer=n;
        }else{
            lastPointer.right=n;
            n.left=lastPointer;
            lastPointer=n;
        }
        toll(n.right);
    }
}