void printPaths(struct node* node) {
int path[1000];

printPathsRecur(node, path, 0);
}

/*
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.
*/
void printPathsRecur(struct node* node, int path[], int pathLen) {
if (node==NULL) return;

// append this node to the path array
path[pathLen] = node->data;
pathLen++;

// it's a leaf, so print the path that led to here
if (node->left==NULL && node->right==NULL) {
printArray(path, pathLen);
}
else {
// otherwise try both subtrees
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}

// Utility that prints out an array on a line.
void printArray(int ints[], int len) {
int i;
for (i=0; i<len; i++) {
printf("%d ", ints[i]);
}
printf("\n");
}

I forgot to put

 and 

How about a solution that explores the whole search space?

For each node in tree: Explore(List<Node>, remaining_sum)

List<Node> stores path so far

Explore (List<Node>, remaining_sum)
	Current_node = last_node_in_list
	If coming from parent (i.e., last node in List is child of second-last node in List)
		if (current_node->left_child exists)
			Add to List: current_node->left_child
			remaining_sum -= value(current_node->left_child)
			// check_and_print
			if (remaining_sum == 0)
				print List
				return
			if (remaining_sum < 0)
				return
			Explore (List<Node>, remaining_sum)
		// do similalrly for right child

// do similarly if coming from bottom-left and bottom right
	If coming from bottom-left
		Explore (parent,remaining_sum)
		Explore (right_child, remaining_sum)
	If coming from bottom-right
		Explore (parent,remaining_sum)
		Explore (left_child, remaining_sum)

I can change the solution to including the sum, but still my solution will be from the path. Any hints?

void printPaths(struct node* node) {
int path[1000];

printPathsRecur(node, path, 0, sum);
}

void printPathsRecur(struct node* node, int path[], int pathLen, int sum) {
if (node==NULL) return;

// append this node to the path array
path[pathLen] = node->data;
pathLen++;
sum=sum - node->data;

if (sum==0) {
printArray(path, pathLen);
}
else {
printPathsRecur(node->left, path, pathLen, sum-node->left.data);
printPathsRecur(node->right, path, pathLen, sum-node->right.data);
}
}

// Utility that prints out an array on a line.
void printArray(int ints[], int len) {
int i;
for (i=0; i<len; i++) {
printf("%d ", ints[i]);
}
printf("\n");
}

void findsum(node* head, int sum, int* buffer, int level)
{
if(*head==NULL)
return;

int temp = sum;
buffer[level] = head->data;
for(int i = level; i>=0;i--)
{
temp = temp - buffer[i];
if(temp==0)
print(buffer, level, i);
}
findsum(head->left, sum, buffer, left+1);
findsum(head->right, sum, buffer, left+1);
}

void print(int* buf, int start, int end)
{
for(int i = start;i<=end;i++)
{
printf(buffer[i]);
}
}

From root node, DFS and calculate the sum value of path from root node to any left nodes and right nodes in tree.
Also, you can know the sum value of path from any node to its left children and right children.

To each node, calculate the sum of a left child path value and a right child path value, You can get the answer.

void printPaths(struct node* node) {
int path[1000];

printPathsRecur(node, path, 0, sum);
}

void printPathsRecur(struct node* node, int path[], int pathLen, int sum) {
if (node==NULL) return;

// append this node to the path array
path[pathLen] = node->data;
pathLen++;
sum=sum - node->data;

if (sum==0) {
printArray(path, pathLen);
}
else {
printPathsRecur(node->left, path, pathLen, sum);
printPathsRecur(node->right, path, pathLen, sum);
}
}

// Utility that prints out an array on a line.
void printArray(int ints[], int len) {
int i;
for (i=0; i<len; i++) {
printf("%d ", ints[i]);
}
printf("\n");
}

hi thr... i'm giving this algorithm.... havnt checked it but i think i'll work...
It doesnt need any array to store the path or something...
It assumes the following structure...

struct node
{
      struct node *left,*right,*parent;
      int data;
};
typedef struct node *Node;

void PrintAllPaths(Node root,int currentSum, int totalSum)
{
       if(root==NULL)return;

if(root->data==currentSum)
       {
               printPath(root,sum);  //print the currently found path separately
       }
       else
       {
               printAllPaths(root->left, currentSum-root->data ,totalSum);
               printAllPaths(root->left, currentSum-root->data ,totalSum);
       }   
       
/*But to cover the entire possibilities u must not return from here otherwise the solution paths starting from root->left or root->right will remain unexplored.   
*/
       printAllPaths(root->left, totalSum ,totalSum);
       printAllPaths(root->right, totalSum ,totalSum);

return;  
}
   
void printPath(Node root,int sum)
{
       if(root->key==sum)
               printf(" %d ",root->key);
      
       else
          printPath(root,sum-root->key);
          printf(" %d ",root->key);
   
       return;
}

hi thr... i'm giving this algorithm.... havnt checked it but i think i'll work...
It doesnt need any array to store the path or something...
It assumes the following structure...

struct node
{
      struct node *left,*right,*parent;
      int data;
};
typedef struct node *Node;

void PrintAllPaths(Node root,int currentSum, int totalSum)
{
       if(root==NULL)return;

if(root->data==currentSum)
       {
               printPath(root,sum);  //print the currently found path separately
       }
       else
       {
               printAllPaths(root->left, currentSum-root->data ,totalSum);
               printAllPaths(root->left, currentSum-root->data ,totalSum);
       }   
       
/*But to cover the entire possibilities u must not return from here otherwise the solution paths starting from root->left or root->right will remain unexplored.   
*/
       printAllPaths(root->left, totalSum ,totalSum);
       printAllPaths(root->right, totalSum ,totalSum);

return;  
}
   
void printPath(Node root,int sum)
{
       if(root->key==sum)
               printf(" %d ",root->key);
      
       else
          printPath(root,sum-root->key);
          printf(" %d ",root->key);
   
       return;
}

// This code tries to avoid doing the recursion twice... 
void printPathSum(struct node* node, int totalSum) {
 int path[1000];


printPathsRecur(node, path, 0, totalSum, 0, 0);
}

void printPathSumRecur(struct node* node, int path[], int pathLen, int totalSum, int curSum, int sumIdx0) {
 if (node==NULL) return;

// append this node to the path array
 path[pathLen] = node->data;
 pathLen++;

if(curSum==totalSum) 
    printpath(path, sumIdx0, pathLen);

while(curSum>=totalSum)curSum-=path[sumIdx0++];

// otherwise try both subtrees
   printPathSumRecur(node->left, path, pathLen, totalSum, curSum+node->data, sumIdx0);
   printPathSumRecur(node->right, path, pathLen,totalSum, curSum+node->data, sumIdx0);
}

// Utility that prints out an array on a line.
void printArray(int ints[], int initidx, int len) {
 int i;
 for (i=initidx; i<len; i++) {
   printf("%d ", ints[i]);
 }
 printf("\n");
}

void PrintSumPaths(Node* n, int sum)
{
if(NULL == n)
return;

if(n->_left == NULL && n->_right == NULL && n->_data && sum == n->_data)
{
printf("Found the path\n");
}

if(n->_left)
{
PrintSumPaths(n->_left, sum);
PrintSumPaths(n->_left, sum - n->_data);
}

if(n->_right)
{
PrintSumPaths(n->_right, sum);
PrintSumPaths(n->_right, sum - n->_data);
}
}

public void ExploreAllPaths(Tree root, int[] path, int pathLength, int remainingSum)
        {
            if (root == null)
                return;


remainingSum -= root.Data;

if (remainingSum >= 0)
            {
                path[pathLength] = root.Data;
                pathLength++;

if (remainingSum > 0)
                {
                    ExploreAllPaths(root.Left, path, pathLength, remainingSum);
                    ExploreAllPaths(root.Right, path, pathLength, remainingSum);
                }
                else
                {
                    PrintPath(path, pathLength);
                }
            }

ExploreAllPaths(root.Left, path, 0, Sum);
            ExploreAllPaths(root.Right, path, 0, Sum);
        }

If the paths can be from a node in left sub tree to any other node in right subtree lower down in tree excluding the root.. then convert the tree to a graph and then perform DF / BF traversal

For dingxiang/Khoa soln:
I think in recursive call just pass "sum" instead of sum-node.data as we have already done sum=sum-node.data

All solutions above are wrong....
Check with a sample tree:
1
2 3
4 5 6 7

If the desired sum was 8. then all above C codes print 1,2,4,5..Which is incorrect.
@mit's code does not even do that.. it will not print anything...
So the suggestion is whenever the condition root->null is true. It must return level-2.
This level - 2 + 1 will be the array index for the next element on right sub-tree. Thus it will now overwrite
number 4. Which is perfect. Now the nodes in the array will be: 1,2,5 making sum as 8.

guys, could someone explain the complexity(time and space) of above code snippets ... i cant think of a solution better than O(n (logn)^2)..!
btw.. wats the order of finding a subsequence of given sum in an array of integers (+ve and -ve) ? is there a soln better than n^2 ?

Can't DFS solve this problem right away?
What's wrong with using DFS to solve this problem ?

Time complexity for DFS is
O( | V | + | E | ) = O(b^d)

Hi all,

if we can put traverse the binary tree into an array, we can solve it a lil bit faster.

traversal of a tree is o(n) into an array
printing path and summing them is o(n) , i believe that we can make good use of some of the properties of a binary tree 2^d - k and the range of k is the number of nodes @ level d.

and the algo can stop if each and every node's been visited at least once.

HOWEVER
i think the path and the sum can be returned during the traversal phrase
but the array makes printing a random path possible.

Chow Yun Fat.

Solution:
say the number is n.
Do an in-order traveral of the tree until we reach a node that is >= n-1, during in-order traversal, add value of each node into an array [maxlen = n].

Now start a while (true) loop.
start from array[0] and calculating the sum till sum = n. If during the loop, sum > n, reset sum = 0 and re-start summing from index 1 of the array... till all the elements of the array have been examined. Since we have to find all the paths, when sum = n, print out the elements of the array from starting index to the point where sum was found.

Key point is that paths in a tree have to be made of consecutive nodes and secondly in this case an in-order traveral will give us the nodes in sorted order.

too lazy to give pseudo code :p

I cogitate this works
Run a BFS on the BST and see if the sum is <=0 if so then check all the paths in that sub tree
and keep on reducing the sum and if at any point the sum is zero print it..

void callPath(node *node,int sum){
	int path[1000];
	struct node* temp;
	Queue q=new Queue();
	if(node==NULL) return;
	else
		q.enqueue(node);


while(!q.isempty(){
		temp=q.dequeue();
		if(temp->data<=sum)
			hasPath(temp,sum,path,0);
		if(temp->left)
			q.enqueue(temp->left);
		if(temp->right)
			q.enqueue(temp->right);
	}
}

void hasPath(node* node,int sum,int[] path,int pathLen){
	if(node==null) return;
	else{
		path[pathLen]=node->data;
		pathLen++;
		int sub=sum-node->data;
		if(sub==0)
			print(path,pathLen);
		hasPath(node->left,sub,path,pathLen);
		hasPath(node->right,sub,path,pathLen);

}
}

void print(int[] path,int pathLen){
	for(int i=0;i<pathLen;i++)
		print(pathLen[i]);
}

Sorry I was not clear in the previous post..

Run a BFS on the BST and see if the sum is <= to the current node value if so check all the paths from the nodes
and recursively reduce the sum and at any point if we see that sum is zero print the path...

void callPath(node *node,int sum){
	int path[1000];
	struct node* temp;
	Queue q=new Queue();
	if(node==NULL) return;
	else
		q.enqueue(node);

while(!q.isempty(){
		temp=q.dequeue();
		if(temp->data<=sum)
			hasPath(temp,sum,path,0);
		if(temp->left)
			q.enqueue(temp->left);
		if(temp->right)
			q.enqueue(temp->right);
	}
}

void hasPath(node* node,int sum,int[] path,int pathLen){
	if(node==null) return;
	else{
		path[pathLen]=node->data;
		pathLen++;
		int sub=sum-node->data;
		if(sub==0)
			print(path,pathLen);
		else{
			hasPath(node->left,sub,path,pathLen);
			hasPath(node->right,sub,path,pathLen);
		}
	}
}

void print(int[] path,int pathLen){
	for(int i=0;i<pathLen;i++)
		print(pathLen[i]);
}

My idea:

1. First of all, consider the core of this problem: it is asking for a continuous subset sum in an array, e.g.

0 1 2 3 4 5 6
8 1 5 2 4 3 7

we should be able to finish finding the subset in O(n) time. This can be done with augmentation every a[i] with a sum from a[0] to a[i], plus a hashtable containing all these sums. When we come to a[i], we can immediately know whether and where is the starting point of such a subset.

2. Then we can augment the tree nodes with the sum from the root to the current node. And then, perform DFS on the tree, and build the hashtable of the current path up to the current depth with O(1) per recursion. With the augmentation and the dynamic hashtable, this is essentially the same as 1. The whole algorithm should be able to finish in O(n).

Guys,
First of all can there be more than one such path assuming the sum input is greater than the largest value in the tree (If it is lesser there is the trivial solution of the element itself, if it exists). I am guessing there is only one such path because of the nature of the BST. In which case it is possible to find that path in O(n) time (depth-first maybe).

Hi Eric,

Consider a BST:
10
5 12
2 8 11 15

And the request is for sum = 15.
there are 2 paths: 10 - 5, 15.

I think your doubt should be cleared. Moreover, the problem does not indicate any condition on the sum requested, So it would complicate if we were to assume that it is greater, equal or smaller than the maximum element.

This is my solution

 
	public List<Path> findPaths(int value)
	{
		List <Path> candidatePaths = findPaths(root, value);
		List <Path> paths = new ArrayList<Path>();
		for(Path candidatePath:candidatePaths)
		{
			if(candidatePath.isComplete())
				paths.add(candidatePath);
		}
		return paths;
	}
	
	public List <Path> findPaths(Node node, int value)
	{
		// this returns completed paths of value or incomplete paths of lesser value
		if(node == null)
			return null;
		
		List <Path> paths = new ArrayList<Path>();
		List <Path> leftPaths = null;
		List <Path> rightPaths = null;
		
		Path thisPath = new Path(node);
		if(node.getValue() == value)
			thisPath.setCompleted(true);
		paths.add(thisPath);
		if(node.getLeft() != null)
		{
			 leftPaths = findPaths(node.getLeft(), value);
			 
		}
		if(node.getRight() != null)
		{
			 rightPaths = findPaths(node.getRight(), value);
			 
		}
		if(leftPaths != null)
		{
		
			for(Path path:leftPaths)
			{
				path = (Path)path.clone();
				if(path.isComplete())
				{
					paths.add(path);
					continue;
				}
					
				path.insertRight(node);
				if(path.getCount() == value)
					path.setCompleted(true);
				paths.add(path);	
				
				
			}
		}
		if(rightPaths != null)
		{
			for(Path path:rightPaths)
			{
				path = (Path)path.clone();
				if(path.isComplete())
				{
					paths.add(path);
					continue;
				}
					
				path.insertLeft(node);
				if(path.getCount() == value)
					path.setCompleted(true);
				paths.add(path);	
			}
		}
		
		if(leftPaths != null && rightPaths != null)
		{
			for(Path path:leftPaths)
			{
				if(path.isComplete() != true)
				{
					for(Path rightPath:rightPaths)
					{
						if(rightPath.isComplete() != true)
						{
							if(path.getCount() + node.getValue() + rightPath.getCount() == value)
							{
								Path newPath = (Path)path.clone();
								newPath.insertRight(node);
								newPath = newPath.mergeRight(rightPath);
								newPath.setCompleted(true);
								paths.add(newPath);
							}
						}
					}
				}
			}
		}
		
		return paths;
	}


class Path implements Cloneable
	{
	
		private List <Node> nodeList;
		private int count = 0;
		
		boolean completed = false; 
		public Path()
		{
			nodeList = new ArrayList<Node>();
		}
		 
		public Path(Node node)
		{
			nodeList = new ArrayList<Node>();
			nodeList.add(node);
			count += node.getValue();
		}
		
		public boolean isComplete()
		{
			return completed;
		}
		
		public void setCompleted(boolean completed)
		{
			this.completed = completed;
		}
		
		public Node getLeftNode()
		{
			if(nodeList.size() > 0)
				return nodeList.get(0);
			else
				return null;
		}
		
		public Node getRightNode()
		{
			if(nodeList.size() > 0)
				return nodeList.get(nodeList.size() - 1);
			else
				return null;

}
		
		public void insertLeft(Node node)
		{
			nodeList.add(0, node);
			count += node.getValue();
		}
		
		public void insertRight(Node node)
		{
			nodeList.add(nodeList.size() - 1, node);
			count += node.getValue();
		}
		
		public int getCount()
		{
			return this.count;
		}
		
		public Object clone()
		{
			Path clone = new Path();
			clone.nodeList.addAll(this.nodeList);
			//Collections.copy(clone.nodeList, this.nodeList);
			clone.count = this.count;
			clone.setCompleted(this.completed);
			return clone;
		}
		
		public Path mergeRight(Path rightPath)
		{
			Path newPath = (Path)this.clone();
			newPath.nodeList.addAll(rightPath.nodeList);
			newPath.count += rightPath.getCount();
			return newPath;
		}

}

I believe this is the correct solution:

(it is not my credit, I just copy and paste from techinterview discussion.)
If you must start at the root, then the following will work (but can probably be improved upon):

Traverse your tree, changing it so that the value at each node changes to the value of it's parent node + it's original value. Thus the values are in this tree are the sum of the values in the unchanged tree from the root to the given point. If the value you currently have is the one you want, then add the path to this node to your list.

If you don't have to start at the root, then traverse your tree as before, but at each node replace its value with a list containing it's original value (head of the list), and its's original value summed with each element of it's parent's list (tail of list). Thus each node has a list of numbers, indicating the sum to that node starting from different ancestors, the number of ancestors required being the position in the list. If any of these values turn out to be the one you want, then store it in the list.

NB The above methods take no advantage of it being a binary search tree. A simple improvement is found by knowing that if your current value is too high and current node is non-negative, then you only need to search the left-hand branch. Similarly, if your current value is too low and the current node is non-positive, only search the right-hand tree. If you know in advance that the numbers are all non-negative or all non-positive, then you can stop searching altogther when you reach a sum that is too high/too low. (Stop at a value that is too extreme in the second algorithm).

If the paths must stop at a leaf, traverse the tree as above, but only store paths that sum to the correct value if they are a leaf node. Speed-ups still apply.

Queue q;

void PrintPath(node *root,int sum)
{

if(root == NULL || sum < 0)
return;

CheckPathPresent(root,sum);
PrintPath(root->right,sum);
PrintPath(root->left,sum);
}

void CheckPathPathPresent(node *root,int sum)
{

if(root == NULL || sum < 0)
return;

int Diff = sum - root->Data;
q.Push(root->Data);
if(Diff == 0)
{
q.PrintQueue();
}
else
{
CheckPathPresent(root->left,Dif);
CheckPathPresent(root->right,Dif);
}
q.Pop(root->Data);
}

@dawninghu,

Your solution looks correct.Its great to have such solution. But I feel that your solution has lottttt of memory requirement. At each node, you are storing almost n (let n is total number of nodes in tree) , you are consuming O(n2) space and that too , at each node, it wil take some good amount of time to traverse the array list.

My proposal is as follows:

Let the height of tree is k.
then create an k*k matrix. In this matrix, we will store the sum of distances from node at level 1...k to node at level 1..k .

0 1 2 3 4 5
1
2 0
3 0 0
4 0 0 0
5 0 0 0 0

so each element M(i,j) gives length of path from i to j.
so all lower triangle elements are 0.

now, traverse along the left most branch and update the matrix . it can be done very easily. If any value is the value we are looking for, then make a note of i and j values.
Now, go to one level up in the tree from the last node. So the last column and last row is invalid, but all others same. so, for nodes starting from this uplevel, add extra rows and columns to the matrix. start searching on the this upper level in the same way as we did earlier.

By doing this, we are not doing any extra calculations, i mean we are not calcuating any sum of lengths we already calculated, but we are reusing them by adding rows and colums of new nodes we find .

I think I didn't explain the algorithm in an easy understandable way. But try to get the essence in it.

BST does not have to be directed, right? And has anybody mentioned the situation shown in the following example?

level node.data left_child.data right_child.data
0 20 7 21
1 7 3 9
1 21 null null
2 3 2 5
2 9 8 10
3 2 null null
3 5 null null
3 8 null null
3 10 null null

If I ask you to find path whose sum is 21, you should return two paths: 2->3->7->9 and 21

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


typedef struct node
{
	int data;
	struct node *left;
	struct node *right;
}Node;
typedef struct queue 
{
	Node * cell;
	struct queue *next;
}Queue;

void Enqueue(Queue **head, Node *temp)
{
	Queue *current = *head;

Queue *newNode = (Queue *)malloc(sizeof(Queue));
	newNode->cell = temp;
	newNode->next = NULL;

if(NULL == *head)
	{
		*head = newNode;
	}
	else
	{
		while(NULL != current->next)
			current = current->next;
		current->next = newNode;
	}
}
Queue * Dequeue(Queue **head)
{
	Queue *temp = *head;
	if(NULL == *head)
		return NULL;
	else
	{
		*head = (*head)->next;
	}
	return temp;
}

Node * newNode(int val);
Node * insertNode(Node *, int);
Node * buildBST(Node *);
void inorder(Node *root);
int lookUp(Node *root, int val);
int pathSum(Node *, int);
void printArray(int path[], int len);
void pathSum(Node *root, int path[], int pathlen, int sum);
void levelOrder(Node *root);
void hasSum(Node *root);

#define ORIG_SUM 8

int main()
{
	Node *root = NULL;

//int path[100];

root = buildBST(root);
	printf("\nInorder traversal is : \n");
	inorder(root);
	printf("\n\n");
	
	//pathSum(root, path, 0, ORIG_SUM);
	levelOrder(root);

return 0;
}
void levelOrder(Node *root)
{
	Queue *head = NULL;
	Enqueue(&head,root);

while(NULL != head)
	{
		Queue *temp = Dequeue(&head);
		hasSum(temp->cell);
		if(temp->cell->left != NULL)
		{
			Enqueue(&head,temp->cell->left);
		}
		if(temp->cell->right != NULL)
		{
			Enqueue(&head, temp->cell->right);
		}
	}
}
void hasSum(Node *root)
{
	int path[100];
	pathSum(root, path, 0, ORIG_SUM);
}
void pathSum(Node *root, int path[], int pathlen, int sum)
{
	if(NULL == root)
		return;
	//append this node the current array
	path[pathlen] = root->data;
	++pathlen;
	sum = sum - root->data;

if(0 == sum)
	{
		printArray(path, pathlen);
	}
	else
	{
		pathSum(root->left,path, pathlen,sum);
		pathSum(root->right,path, pathlen,sum);		
	}
	
}
void printArray(int path[], int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		printf("%d\t", path[i]);
	}
	printf("\n\n");
}
Node * newNode(int val)
{
	Node *temp = (Node *)malloc(sizeof(Node));

if(NULL != temp)
	{
		temp->data = val;
		temp->left = NULL;
		temp->right = NULL;
	}
	else
		exit(1);

return temp;
}
Node * insertNode(Node *root, int val)
{
	if(NULL == root)
		return newNode(val);
	else
	{
		if(val < root->data)
			root->left = insertNode(root->left, val);
		else
			root->right = insertNode(root->right, val);

return root;
	}
}
Node * buildBST(Node * root)
{
	int n;
	int val;
	int i;
	int A[] = {5,3,7,2,4,6,8};

printf("\nHow many nodes in the tree ? ");
	scanf("%d", &n);

srand(time(NULL));

for(i=0;i<n;i++)
	{
		/*val = rand()%98 + 1;
		if(!lookUp(root, val))
		{
			root = insertNode(root, val);
		}
		else
		{
			printf("\nDuplicate value\n");
		} */
		root = insertNode(root, A[i]);
	}
	printf("\nInsertion Done !\n");

return root;
}
int lookUp(Node *root, int val)
{
	if(NULL == root)
	{
		return 0;
	}
	else
	{
		if(val == root->data)
			return 1;
		else if(val < root->data)
			return lookUp(root->left, val);
		else
			return lookUp(root->right, val);
	}
}
void inorder(Node *root)
{
	if(NULL == root)
		return;
	else
	{
		inorder(root->left);
		printf("%d\t", root->data);
		inorder(root->right);
	}
}

std::vector< std::vector<int> > pathToNum(bt_t* root , int num)
{


std::vector< std::vector<int> >resVec;
    std::vector<int> tempVec;

if(!root){
        return resVec;
    }

std::stack< bt_t* > nst;
    std::stack<int> sst;
    std::stack< std::vector<int> > vst;

nst.push(root);
    sst.push(num-root->data);

tempVec.push_back(root->data);
    vst.push(tempVec);

while(!nst.empty())
    {
        bt_t* cur = nst.top();
        nst.pop();

int sum = sst.top();
        sst.pop();

std::vector<int> tempVec = vst.top();
        vst.pop();

int a = tempVec.size();

if(sum<0){
            while(sum<0){
                if(!tempVec.empty()){
                    sum+= tempVec[0];
                    tempVec.erase(tempVec.begin());
                }
                else
                    sum = num;
            }
        }

if(sum==0)
        {
            if(tempVec.size()>1)
            {
                resVec.push_back(tempVec);
                sum+= tempVec[0];
                tempVec.erase(tempVec.begin());
            }
        }

if(cur->right){
               nst.push(cur->right);
               sst.push(sum-cur->right->data);
               tempVec.push_back(cur->right->data);
               vst.push(tempVec);
               tempVec.pop_back();
        }

if(cur->left){
               nst.push(cur->left);
               sst.push(sum-cur->left->data);
               tempVec.push_back(cur->left->data);
               vst.push(tempVec);
               tempVec.pop_back();
        }
    }

return resVec;
}

No extra space is needed.
Tested on Visual Studio.

<<
bool find(Node* node, int sum)
{
if (!node)
return false;
else if (sum-node->value==0){
cout<<node->value;
return true;
}
else{
bool found=false;
if (find(node->left, sum-node->value)){
cout<<node->value;
found=true;
}
if(find(node->right, sum-node->value)){
cout<<node->value;
found=true;
}
return found;
}
}

void traverse(Node* node, int sum){
if (!node)
return ;
find(node, sum);
traverse(node->left, sum);
traverse(node->right, sum);
}

int main(){
traverse(root, 100);
}

>>

package com.dale.topcoders;


import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class TreeWithParent {

private class node {
		int data;
		node left;
		node right;
		node parent;
	}

static node root;

public void insertNode(int data) {
		if (root == null) {
			root = new node();
			root.data = data;
			root.left = null;
			root.right = null;
			root.parent = null;
			return;
		}
		node cur = root;
		if (cur.left != null) {
			while (cur.left != null && cur.data > data) {
				cur = cur.left;
			}
		}

if (cur.right != null) {
			while (cur.right != null && cur.data < data) {
				cur = cur.left;
			}
		}
		node temp = new node();
		temp.data = data;
		temp.left = null;
		temp.right = null;

if (data > cur.data) {
			cur.right = temp;
		} else {
			cur.left = temp;
		}
		temp.parent = cur;
	}

private void bfs() {
		Queue<node> q = new ArrayBlockingQueue<node>(20);
		node cur = root;
		if (root == null) {
			System.out.println("Empty Graph!");
			return;
		}
		q.add(cur);
		while (q.isEmpty() == false) {
			node top = q.remove();
			if (top != null) {
				System.out.print(" Q : " + top.data);
				if (top.parent != null)
					System.out.print(" and its parent is " + top.parent.data);
				System.out.println("");
				if (top.left != null) {
					q.add(top.left);
				}
				if (top.right != null) {
					q.add(top.right);
				}
			}
		}
	}

public void printAllPaths(node cur, int curSum, int totalSum) {
		if (cur == null) {
			System.out.println("Empty List ! Cannot Print");
			return;
		}

if (cur.data == curSum) {
			System.out.println("Found!");
			printPath(cur, totalSum);
		} else {
			if (cur.left != null)
				printAllPaths(cur.left, curSum - cur.data, totalSum);
			if (cur.right != null)
				printAllPaths(cur.right, curSum - cur.data, totalSum);
		}
		if (cur.left != null)
			printAllPaths(cur.left, curSum - cur.data, totalSum);
		if (cur.right != null)
			printAllPaths(cur.right, curSum - cur.data, totalSum);
	}

private void printPath(node cur, int sum) {
		if (cur != null) {
			if (cur.data == sum) {
				System.out.println(" " + cur.data);
			} else {
				printPath(cur.parent, sum - cur.data);
			}
			System.out.println(" " + cur.data);
			return;
		}
	}

/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

TreeWithParent tree = new TreeWithParent();
		tree.insertNode(5);
		tree.insertNode(2);
		tree.insertNode(7);
		tree.insertNode(1);
		tree.insertNode(3);
		tree.insertNode(9);
		tree.bfs();
		node cur = root;
		tree.printAllPaths(cur, 12, 12);
	}

}

void PrintPath(t* root, int* a, int start, int end, int ori_sum)
//a[] is an predefined empty array, initial value for start and end is 0
{
if(!root) return;
a[end++]=root->val;
for(int i=start;i<end;i++)
sum+=a[i];
if(sum>=ori_sum)
{
if(sum==ori_sum)
{
for(int i=start;i<end;i++)
cout<<a[i];
}
start++;
}
PrintPath(root->left,int* a,int start, int end,int val);
PrintPath(root->right,int* a,int start, int end,int val);
}

bool.find_sum(node*.root,.int.sum,.int*.a,.int.n){
..if.(!root)
......return.false;
..a[n].=.root->n;
..++n;
..if.(sum.-.root->n==0){
......for(int.i=0;i<n;++i)
..........cout.<<.a[i]<<.".";
......return.true;
..}else{
......if.(find_sum(root->left,.sum-root->n,.a,.n)){
..........return.true;
......}
......if(find_sum(root->right,.sum-root->n,.a,.n)){
..........return.true;
......}
......return.false;
..}
}

void.traverse_sum(node*.root,.int.sum){
..if.(!root)
......return.;
..int.a[100];
..int.l.=.100;
..find_sum(root,.sum,.a,.0);
..cout.<<."\n";
..traverse_sum(root->left,.sum);
..traverse_sum(root->right,.sum);
}

Brute force method: can be done by modifying tree traversal method to include variable arguments containing the key values from the root to the parent.

At the current node, copy the variable arguments to an array (or a linked list) check whether any contiguous subsequence sum of numbers from the root the current node adds up to the given number.

Checking whether any contigious subsequence sum adds up to the given number can be solved in O(n) using the following algo.

maintain two indices startIndex and endIndex. Initially they both point to the beginning to of the array. Take a variable runningSum and initialise it to 0.

while (runningSum != givenSum && endIndex < length(arr))
{
if (runningSum < givenNumber) runningSum += arr[endIndex++];
else if (runningSum > givenNumber) runningSum == arr[startIndex--];
}

if (endIndex >= length(arr))
return notfound
else
print startIndex, endIndex.

PrintPath(root, sum, 0, 0, list, listOfList);
void PrintPath(node root,int remains,int start, int end, List<int> list, List<List<int>> listOfList)
{
	if(root == null)
		return;


int tempStart = start;
	while(root.data > remains && tempStart != end)
	{
		remains = remains + list[0];
		tempStart++;
		
	}

if(root.data == remains)
	{
		List<int> temp = DeepCopy(list, tempStart, end);
		listOfList.Add(temp);
	}

if(root.data > remains)
		return;

end = end + 1;
	remains = remains - root.data;
	list.Add(root.data);
	PrintPath(root.left,tempStart, end, remains, list, listOfList);
	PrintPath(root.right,tempStart, end, remains, list, listOfList);
	list.Remove(list.Count-1);
}
Sum: 21,11,6

10
       /    \
      5     11
     / \
    4   6
   / 
  2   
Sum:5
        5
       /
      4
     /
    1

I think one needs to traverse the whole tree and search each sub-tree at every node for the sum. so complexity is n log n.