Print all the paths in a BST which sum is equal to given value

Problem
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode
{
int data;
struct TreeNode *left, *right;
}TreeNode;

typedef TreeNode *Tree;

/*
    Return Value:
    0 : Success
    -1: Failure

    Prints the path in reverse order
 */

int printpaths(int sum, Tree t, int isRoot)
{
if(t == NULL)
{
return -1;
}
int ret = -1;

int n = sum - t->data;

if(n == 0)
{
printf("%d%c", t->data, isRoot?'\n':' ');
ret = 0;
}
else if(n > 0)
{
if(printpaths(n, t->left, 0) == 0)
{
printf("%d%c", t->data, isRoot?'\n':' ');
ret = 0;
}

if(printpaths(n, t->right, 0) == 0)
{
printf("%d%c", t->data, isRoot?'\n':' ');
ret = 0;
}
}

printpaths(sum, t->left, 1);
printpaths(sum, t->right, 1);

return ret;
}

TreeNode *makeTreeNode(int d)
{
TreeNode *t = calloc(1, sizeof(TreeNode));
t->data = d;
}

int main()
{
Tree t = makeTreeNode(80);

t->left = makeTreeNode(60);
t->left->left = makeTreeNode(50);
t->left->left->left = makeTreeNode(30);

printpaths(140, t, 1);
}
Advertisements

2 thoughts on “Print all the paths in a BST which sum is equal to given value

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