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.

Maximum distance between any two nodes of a Binary Tree (a.k.a Diameter or Width of the Tree)

Question: Given a binary tree, write a program to find maximum distance between any two nodes of the tree.

Time Complexity: O(n)

int

diameter(tree *t)
{
    /* left diamter, right diameter, node diameter */
    int ld, rd, nd;

    if (!t) {
        return 0;
    }

    ld = diameter(t->left);
    rd = diameter(t->right);
    nd  = height(t->left) + height(t->right) + 1;

    return max3(ld, rd, nd);
}

Slightly more efficient algorithm, this calculates the height of the tree along with diameter.

int
diameter2(tree *t, int *height)
{
    /* left diameter, right diameter, node diameter */
    int ld, rd, nd;

    /* left height, right height */
    int lh, rh;

    if (!t) {
        *height = 0;
        return 0;
    }

    ld = diameter2(t->left, &lh);
    rd = diameter2(t->right, &rh);
    nd  = lh + rh + 1;

    *height = max(lh, rh) + 1;
    return max3(ld, rd, nd);

}

max3 - returns maximum of the three arguments

Height of a Binary Tree

Question: Given a binary tree, write a program to find height of the tree.

Time Complexity: O(n)

int
height(tree *t)
{
    int lh, rh;

    if (!t) {
        return 0;
    }

    lh  = height(t->left);
    rh = height(t->right);

    return max(lh, rh) + 1;

}