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