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