Tree - List Problem

Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes.

/********************************************************
 ****      The Great Tree List Recursion Problem     ****
 *******************************************************/
struct node;

typedef struct node *nodeptr;

struct node {
    nodeptr left;
    int data;
    nodeptr right;
};

/*
 * given two list nodes, join them together so the second
 * immediately follows the first.
 */
void join(nodeptr a, nodeptr b)
{
    a->right = b;
    b->left = a;
}
/*
 * given two circular doubly linked lists, append them
 * and return the new list.
 */
nodeptr append(nodeptr a, nodeptr b)
{
    nodeptr aLast, bLast;

    if(a == NULL) return b;
    if(b == NULL) return a;
   
    aLast = a->left;
    bLast = b->left;

    join(aLast,b);
    join(bLast,a);

    return a;
}
/*
 * Convert given BST to linked list
 */
nodeptr treeToList(nodeptr root)
{
    nodeptr aList, bList;
    if(root == NULL)
        return NULL;
    else {
        aList = treeToList(root->left);
        bList = treeToList(root->right);
       
        root->left = root;
        root->right = root;
       
        aList = append(aList, root);
        aList = append(aList, bList);

        return aList;
    }
}
/*
 * print circular doubly linked list
 */
void printList(nodeptr head)
{
    nodeptr temp = head;
    if(head != NULL) {
        while(head->right != temp) {
            printf("%d ", head->data);
            head = head->right;
        }
        printf("%d ", head->data);
    }
    printf("\n");
}

Given a Binary Tree check whether it is Binary Search Tree or not

Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.

/*
 * Is BST helper function
 */
int isBSTUtil(nodeptr node, int min, int max)
{
    if(node != NULL)
        return (node->data >= min && node->data <=max) &&
            isBSTUtil(node->left, min, node->data) &&
            isBSTUtil(node->right, node->data, max);
    return 1;
           
}
/*
 * determine given binary tree is BST
 */
int isBST(nodeptr node)
{
    int min,max;
    if (node != NULL) {
        min = minValue(node);
        max = maxValue(node);
        return isBSTUtil(node, min, max);
    }
    return 1;
}

Check given two binary trees are same or not

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.



/*
 * Compare two binary tree and return true if they are
 * structurally identical.
 */
int sameTree(nodeptr a, nodeptr b)
{
    if(a == NULL && b == NULL)
        return 1;
    else if((a == NULL && b != NULL) || (a != NULL && b == NULL))
        return 0;
    else {
        return (a->data == b->data && sameTree(a->left, b->left) &&
                sameTree(a->right, b->right));
    }
}

Print all paths of Binary Tree

Given a binary tree, print out all of its root-to-leaf paths.

/*
 * Print array
 */
void printArray(int *path, int pathlen)
{
    int i;
    for(i = 0; i < pathlen; i++) {
        printf("%d ",path[i]);
    }
    printf("\n");
}
/*
 * Helper function to print all paths
 */
void printPathsRecur(nodeptr node, int path[], int pathLen)
{
    path[pathLen] = node->data;
    pathLen++;
    if(node->left == NULL && node->right == NULL) {
        printArray(path, pathLen);
    } else {
        printPathsRecur(node->left, path, pathLen);
        printPathsRecur(node->right, path, pathLen);
    }
}
/*
 * Print all paths
 */
void printPaths(nodeptr node)
{
    int path[200];
    if(node != NULL)
    {
        printPathsRecur(node, path, 0);
    }
}

hasPathSum - Binary Tree

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values
along the path equals the given sum. Return false if no such path can be found.

So for example, the following tree has exactly four root-to-leaf paths:
                       5
                   /        \
                4           8
              /          /       \         
          11         13        4
         /     \                     \
       7       2                    1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

/*
 * "root-to-leaf path" to be a sequence of nodes in a tree
 * starting with the root node and proceeding downward to a leaf.
 */
int hasPathSum(nodeptr node, int sum)
{
    int subsum;
    if(node == NULL) {
        return (sum == 0);
    } else {
        subsum = sum - node->data;
        return (hasPathSum(node->left, subsum) ||
                hasPathSum(node->right, subsum));
    }
}