August 20, 2013

Convert a binary search tree into a sorted doubly link list

Question: Given a binary tree, write a program to convert a binary search tree into a sorted doubly link list (tree->left will be list->prev, while tree->right will be list->next). This is an in-place algorithm with constant space requirement.

Time Complexity: O(n)

void
tree2list(tree *t, tree **prev, tree **head)
{
    if (!t)
        return;

    tree2list(t->left, prev, head);

    if (*prev == NULL) {
        *head = t;
    } else {
        t->left = *prev;
        (*prev)->right = t;
    }
    *prev = t;

    tree2list(t->right, prev, head);

}

This functions is called with prev = NULL, and the head will point to the first node of the doubly link list after the function call.