Thursday, September 22, 2011

Given a binary tree, print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order

Given a binary tree. Find the sum( inclusive of the root ) of sub-tree rooted at each node. Print the sum in in-order.

E.g.

                  3

/ \

2 4

/ / \

2 2 -1

Output: 2, 4, 12, 2, 5, -1.


Solution


#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode
{
struct TreeNode *left, *right;
int data;

}TreeNode;

typedef TreeNode * 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;


}

/*Utilities*/

inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}


int main()
{
/*level 0*/
Tree t = makeTreeNode(3);

/*level 1*/
t->left = makeTreeNode(2);
t->right = makeTreeNode(4);


/*level 2*/
t->left->left = makeTreeNode(2);
t->right->left = makeTreeNode(2);
t->right->right = makeTreeNode(-1);

/*print sum*/
printSum(t, 1);
printf("\n");

int a[100];

int pos = -1;

printSum2(t, a, &pos);

int i;

for(i = 0; i <= pos; ++i) {
printf("%d ", a[i]);
}

printf("\n");

return 0;
}

0 comments:

Post a Comment