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;

}

Mirror a Binary Tree

Question: Given a binary tree, write a program to mirror the tree (i.e. swap left and right nodes of the original tree).

Time Complexity: O(n)


tree *
tree_mirror(tree *t) 
{
    tree *tmp = NULL;

    if (!t) {
        return NULL;
    }

    tmp = (tree *) malloc (sizeof(tree));
    if (!tmp) {
        exit(ENOMEM);
    }

    tmp->data = t->data;
    tmp->right = tree_mirror(t->left);
    tmp->left = tree_mirror(t->right);

    return (tmp);
}

Duplicate a Binary Tree

Question: Given a binary tree, write a program to duplicate the tree (i.e. create an exact copy of the tree).

Time Complexity: O(n)

tree *

tree_duplicate(tree *t) 

{

    tree *tmp = NULL;

    if (!t) {

        return NULL;

    }

    tmp = (tree *) malloc (sizeof(tree));

    if (!tmp) {

        exit(ENOMEM);

    }

    tmp->data = t->data;

    tmp->left = tree_duplicate(t->left);

    tmp->right = tree_duplicate(t->right);

    return (tmp);

}