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

}

Binary Tree Traversal - Recursive and Iterative

Following code illustrates various binary tree traversal algorithms - both recursively and iteratively. All algorithms provided below are DFS algorithms.

Time Complexity: O(n) - for all algorithms

/* recursive pre order traversal */

void pre_order_traversal_recursive(tree2 *t)

{

    if (t == NULL) {

        return;

    }

    /* process node here */

    printf ("%d ", t->data);

    pre_order_traversal_recursive(t->left);

    pre_order_traversal_recursive(t->right);

}

/* recursive in order traversal */

void in_order_traversal_recursive(tree2 *t)

{

    if (t == NULL) {

        return;

    }

    in_order_traversal_recursive(t->left);

    /* process node here */

    printf ("%d ", t->data);

    in_order_traversal_recursive(t->right);

}

/* recursive post order traversal */

void post_order_traversal_recursive(tree2 *t)

{

    if (t == NULL) {

        return;

    }

    post_order_traversal_recursive(t->left);

    post_order_traversal_recursive(t->right);

    /* process node here */

    printf ("%d ", t->data);

}

/* iterative pre order traversal */

void pre_order_traversal_iterative(tree2 *t)

{

    while (t) {

        /* condition to control type of traversal */

        if (((t->left && !t->left->visited) || !t->left) &&

            ((t->right && !t->right->visited) || !t->right)) {

            /* process node here */

            printf("%d ", t->data);

        }

        /* actual tree traversal */

        if (t->left && !t->left->visited) {

            t = t->left;

        } else if (t->right && !t->right->visited) {

            t = t->right;

        } else {

            t->visited = 1;

            t = t->parent;

        }

    }

}

/* iterative in order traversal */

void in_order_traversal_iterative(tree2 *t)

{

    while (t) {

        /* condition to control type of traversal */

        if (((t->left && t->left->visited) || !t->left) &&

            ((t->right && !t->right->visited) || !t->right)) {

            /* process node here */

            printf("%d ", t->data);

        }

        /* actual tree traversal */

        if (t->left && !t->left->visited) {

            t = t->left;

        } else if (t->right && !t->right->visited) {

            t = t->right;

        } else {

            t->visited = 1;

            t = t->parent;

        }

    }

}

/* iterative post order traversal */

void post_order_traversal_iterative(tree2 *t)

{

    while (t) {

        /*

        ** Following condition controls the type of tree traversal

        ** PRE ORDER  : !t->left->visited and !t->right->visited

        ** IN ORDER   :  t->left->visited and !t->right->visited

        ** POST ORDER :  t->left->visited and  t->right->visited

        */

        if (((t->left && t->left->visited) || !t->left) &&

            ((t->right && t->right->visited) || !t->right)) {

            /* process node here */

            printf("%d ", t->data);

        }

        /* actual tree traversal */

        if (t->left && !t->left->visited) {

            t = t->left;

        } else if (t->right && !t->right->visited) {

            t = t->right;

        } else {

            t->visited = 1;

            t = t->parent;

        }

    }

}

Please note that recursive algorithm will also work on regular tree data structure (i.e. without parent and visited). However, iterative algorithms only works with following data structure:

typedef struct tree2_s {

    u32 data; 

    struct tree2_s *left;

    struct tree2_s *right;

    struct tree2_s *parent;

    u32 visited;

} tree2;

Reverse a Singly Linked List - Recursive and Iterative

Question: Write a C program to reverse a singly linked list.

Find below both recursive and iterative functions to reverse a link list. Both functions have same time complexity. Recursive function is called as head = list_reverse1(head, NULL), it returns a pointer to the head of the new list. Iterative function call is self explanatory.

Time Complexity: O(n)

/* recursive */

list *list_reverse_recursive(list *curr, list *prev)
{
    list *head = NULL;

    if (curr == NULL) {
        return prev;
    }

    head = list_reverse_recursive(curr->next, curr);
    curr->next = prev;

    return head;
}

/* iterative */
void list_reverse_iterative(list **head)
{
    list *prev = NULL, *curr = *head, *next = NULL;

    while (curr != NULL) {
        next = curr->next;

        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}

Lowest Common Ancestor

Question: Given values of two nodes in a binary search tree, write a function to find lowest common ancestor of these two nodes. Lowest common ancestor can be described as a parent node that is common and closest to both the given nodes. (If both the nodes are present in the tree the NULL check is not required, also assuming that -1 is an invalid data value.)  


Time Complexity: O(log(n))

int
lowest_common_ancestor(tree *t, int value1, int value2)
{
    // Check required if nodes with input 
    // values are not present in the tree
    if (t == NULL) {
        return -1;
    }


    if (t->data < value1 && t->data < value2) {
        return lowest_common_ancestor(t->right, value1, value2);
    } else if (t->data > value1 && t->data > value2) {
        return lowest_common_ancestor(t->left, value1, value2);
    } else {
        return t->data;
    }

}

Sum of the nodes of binary tree

Question: Write a function to calculate the sum of binary search tree nodes?
Time Complexity: O(n)

int
sum_of_tree_nodes(tree *t)
{
    if (t == NULL) {
        return 0;
    } else {
        return (sum_of_tree_nodes(t->right) +
                t->data                     +
                sum_of_tree_nodes(t->left));
    }
}

String Permutation

Question: Write a program to display all permutation of alphabets in the string ? For example: string 'xyz' has following possible permutations:
xyz
xzy
yxz
yzx
zxy
zyx

// initial call: permutations("xyz", 0)

void permutations(char *str, int level)
{
    int i = 0;
    int len = strlen(str);<br>

    if (level == len)

    {
        // Termination Condition
        printf("%s\n", output);
        return;
    }


    for (i = 0; i < len; i++)
    {
        if (flag[i]) continue;
        output[level] = str[i];
        flag[i] = 1;
        permutations(str, level + 1);
        flag[i] = 0;
    }
}

String Combination

Question: Write a program to display all combinations of alphabets  in a given string ? For example: string 'xyz' has following possible combinations:
x
xy
xyz
xz
y
yz
z

// initial call: combinations("xyz", 0, 0)

void combinations(char *str, int start, int level)

{

    int i = 0;
    int len = strlen(str);

    if (start == len) {

        // Termination Condition

        return;

    }

    for(i = start; i < len; i++)

    {

        output[level] = str[i];

        output[level + 1] = '\0';

        printf("%s\n", output);

        combinations(str, i + 1, level + 1);

    }

}

Fibonacci Number

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 - numbers in this series are known as Fibonacci numbers. By definition, each subsequent Fibonacci number is sum of previous two Fibonacci numbers. First two Fibonacci numbers are 0 and 1.

Write a program to efficiently calculate the Nth Fibonacci number.

Time Complexity: O(n)


unsigned int fibonacci(unsigned int n)

{
    unsigned int n1 = 1, n2 = 0;
    unsigned int x, result;
    
    if (n < 2) {
        return n;
    }
    for (x = 2; x <= n; x++) {
        result = n1 + n2;
        n2 = n1;
        n1 = result;
    }
    return (result);
}

On the contrary, a very simple recursive implementation of fibonacci has exponential complexity.


unsigned int fibonacci(unsigned int n)
{
    if (n < 2) {
        return n;
    }
    return (fibonacci(n - 1) + fibonacci(n - 2));
}

Missing Number

Question: Given an array of integers of size n. This array has integer values starting from x, incrementing by 1. The final array element is n+x (instead of n + x - 1) i.e. it is missing one integer in between. Write a function to identify this missing number.


Example: array[5] = { 2,3,4,6,7 }; missing number is 5.


Time Complexity: O(log n)



int missing_number(int *a, int len)
{
    int mid = len / 2;


    if (len == 1) {
        printf ("missing number is %d\n", a[0] + 1);
        return (a[0] + 1);
    }


    if ((a[0] + mid) == a[mid])
    {
        // first half of array is not missing a number
        missing_number(&a[mid], len - mid);
    } else {
        // second half of array is not missing a number
        missing_number(a, mid);
    }
}

Valid Binary Search Tree

Question: Write a function to find whether a given binary tree is a binary search tree ?


Find below a recursive algorithm to find whether a given binary search tree is valid or not. This algorithm, starting from the root node, at each node verifies whether current node data lies between min and max possible value for that node and also check if the left and right subtree are valid binary search trees. Since node data in my tree is an integer, thus starting min and max values used are 0x80000000 and 0x7fffffff. However, these values will depend on minimum and maximum possible values of the key. In addition, following algorithm assumes no duplicate keys; if duplicate keys are present, the condition in line 8 and 9 needs to be modified.


Time complexity: O(n)


bool
is_valid_bst_helper(tree *t, int min, int max)
{ 
    if (t == NULL) {
        return TRUE;
    }   
  
    if (t->data > min &&
        t->data < max &&
        is_valid_bst_helper(t->left, min, t->data) &&
        is_valid_bst_helper(t->right, t->data, max)) {
        return TRUE;
    }   

    return FALSE;
}

bool
is_valid_bst(tree *t) 
{
    return(is_valid_bst_helper(t, 0x80000000, 0x7fffffff));
}