Thursday, January 5, 2012

print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order in Binary Tree

/*
Two passes with constant space
*/
int printSum(Tree t, int toPrint)
{
    if(t == NULL)
        return 0;

    int lsum = printSum(t->left, toPrint);
    int rsum = printSum(t->right, 0);

    int sum = lsum + t->data + rsum;

    if(toPrint)
        printf("%d ", sum);

    printSum(t->right, toPrint);

    return sum;

}


/*
One pass with n space
*/
int printSum2(Tree t, int a[], int *pos)
{
    if(t == NULL)
        return 0;

    int lsum = printSum2(t->left, a, pos);

    (*pos)++;

    int p = *pos;

    int rsum = printSum2(t->right,a, pos);

    return a[p] = lsum + t->data + rsum;


}

0 comments:

Post a Comment