Unknown - May 1, 2013
the complexity is O(n^2) . since each node is visit multiple times as the traversal is top bottom and not bottom up.
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;
}
Code :
#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;
}