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;
}