CareerCup

but the path ends at that node??

Function Invoked
bt.printPathAnyWhere(node, new int[20], 80, 0);
GivenSum Keeps Decreasing and Main Sum Remains Same

The point of using two functions is to avoid mutiple recursions happening in the same function and avoid printing the same path more than once .

public void printPathAnyWhere(BinaryTreeNode node , int[] a , int mainSum ,int level){
		if(node==null)
			return;
		printPathAnyWhereHelper(node, a, mainSum, 0);
		printPathAnyWhere(node.getLeft(), a, mainSum, 0);
		printPathAnyWhere(node.getRight(), a, mainSum, 0);
	}
	private void printPathAnyWhereHelper(BinaryTreeNode node , int[] a , int givenSum , int level){
		if(node==null){
			return;
		}
		if(node.getValue()==givenSum){
			a[level]=node.getValue();
			System.out.print("Printing Path Any where");
			for (int i = 0; i <= level; i++) {
				System.out.print(a[i]+" ");
			}
			System.out.println();
			return;
		}
		if(node.getValue()<givenSum){
			a[level]=node.getValue();
			printPathAnyWhereHelper(node.getLeft(), a, givenSum-node.getValue(), level+1);
			printPathAnyWhereHelper(node.getRight(), a, givenSum-node.getValue(), level+1);
		}
	}

list<node*> path_sum_seq(node* n, int sum) {
	list<node*> retval;
	if (! n) return	retval;
	if (n->val == sum)
		retval.push_back(n);
	else {		
		retval = path_sum_seq(n->left, sum - n->val, seq);
		if (retval.empty())	
			retval = path_sum_seq(n->right, sum - n->val, seq);
		if (! retval.empty())
			retval.push_back(n);
	}
	return retval;
}

list<node*> path_sum(node* n, int sum) {
	list<node*> retval;
	if (! n) return	retval;
	retval = path_sum(n->left, sum);
	if (retval.empty())	
		retval = path_sum(n->right, sum);
	if (retval.empty())
		retval = path_sum_seq(n, sum - n->val);
}

public class TreePaths {
          static void findSum(TreeNode root,int sum,ArrayList<Integer> buffer,int level)
          {
        	  if(root==null) return;
        	  int temp=sum;
        	  buffer.add(root.data);
        	  for(int i=level;i>-1;i--)
        	  {
        		  temp-=buffer.get(i);
        		  if(temp==0)
        			  print(i,buffer,level);
        	  }
        	  ArrayList<Integer> c1=(ArrayList<Integer>) buffer.clone();
        	  ArrayList<Integer> c2=(ArrayList<Integer>) buffer.clone();
        	  findSum(root.left, sum, c1, level+1);
        	  findSum(root.right, sum, c2, level+1);
        	  
        	  
          }

		private static void print(int level, ArrayList<Integer> buffer, int i2) 
		{
			for(int i=level;i<=i2;i++)
				System.out.print(buffer.get(i)+" ");
			System.out.println();
			
		}
         }

I think this should work

void pathsum(node* n ,int sum, int level)
{
if(n == NULL || sum < 0)
return ;
if(sum == n->data)
{
arr[level] = n->data;
for(int i = 0; i<=level; i++) printf("%d " arr[i]);
return;
}
arr[level] = n->data;
pathsum(n->left,sum-n->data,level+1);
pathsum(n->right,sum-n->data,level+1);
pathsum(n->left,sum,0);
pathsum(n->right,sum,0);
}

I doubt if any of the above codes are really generating all simple paths that sum up to a given target. It's hard to grasp what the code does, as it lacks any explanation.

I contrived an example to start working with. In the below example, target sum = 5. All possible outputs are listed. It'd be nice if you explain (if your program give correct result) the algorithm, and mention the complexity. The lowest achievable TC is O(n^2) as there are O(n^2) simple paths in a tree.

_______________2______________
                /                              \
         _______3______                         5______
        /              \                               \
     __-4               4__                            -2  
    /                      \                                
   _1                       2                                
  /                                                           
  3                                                                           
 /                                                             
 2 

outputs:
3  2  
3  -4  1  3  2  
-4  3  4  2  
2  3  
2  3  -4  1  3  
2  5  -2  
1  -4  3  2  5  -2  

Total # of paths with sum  5 : 7

My approach is like:
- work bottom-up

- each node keeps a list of possible <sum, nodeList> that can be reached to follow descendants. For above example, for node -4, there are three paths with sum -3, 0, 2.

- when moving up, extend all path to the left and right subtrees by including this node.

- finally, consider paths that go across both sides of the nodes.

I believe this approach considers each path only once, and hence leads optimal O(n^2) complexity. Any suggestions are welcomed.

what about this approach... I'm using array as stack

void CheckForSum(int stack[], int stackTop, int sum)
{
	int i = 0;

	for (i = stackTop - 1; i >= 0 && sum > 0; --i)
	{
		sum -= stack[i];
	}

	if (sum == 0 && i >= 0) 
	{
		cout << endl;
		for (int k = stackTop - 1; i < k; --k)
		{
			cout << stack[k] << ", ";
		}
	}
}

void PrintPaths(Node *root, int stack[], int &stackTop, int sum)
{
	if (root)
	{
		stack[stackTop++] = root->data;
		CheckForSum(stack, stackTop, sum);

		PrintPaths(root->left, stack, stackTop, sum);
		PrintPaths(root->right, stack, stackTop, sum);
		
		// Stack Pop
		--stackTop;
	}
}