traversal

                  3  
  
                /  \\  
  
             2       4  
  
           /        /  \\  
  
         2         2   -1  

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