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


Problem
#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;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s