CareerCup

1st question: depth-first search and using a queue to maintain the nodes in the so-far valid path.
Recursively call sum(Node, sum),

sum-=node.value,
if sum==0, print nodes in the queue,
else if sum<0 or node has no child, dequeue and return,
else enqueue(node) sum(left,sum) sum(right,sum)

2nd question: depth-first search and still using a queue(path queue) to maintain a so-far valid path, plus another queue(sum queue) with same length of the path queue, at each element of which the sum starting from that position is stored. i.e.
I have [1,3,5,7,8,9] in path queue(number is the value of each node)
then [33,32,29,24,17,9] in sum queue.
That should speed up the alg.

A little memory efficient is to pass a queue of node from root to current node (and update this LL by remove the tail node (current node) after use). Besides, keep tracking of the current_sum such that if it appears to be > sum, (virtually) remove head of the queue. By virtually means, we are not going to remove it but rather deduct the current_sum with Queue[head] and moves the head index down by one level so that when we have to print out the queue, we simply printout Queue[head] (not always Queue[0]) onward. Note that Queue.get(head) is appeared O(N) but if you implement the LinkedList yourself, we can have Node head instead of int head and then we can directly call head.val instead of Queue.get(head). This will keep the overall complexity O(N).

private void printAll_adv(Node n, int sum, int curr_sum, 
                                  LinkedList<Node> ll, int head) 
        {
		//First, check the possibility
		curr_sum += (int)(n.val - '0');
		ll.add(n);
		if(curr_sum == sum)	printLL(ll,head);
		
		//Keep the curr_sum value < sum before passing
		while(curr_sum > sum && !ll.isEmpty()){
			Node temp = ll.get(head); //BigO of N.
			curr_sum -= (int)(temp.val - '0');
			head++;
			if(curr_sum == sum)	printLL(ll,head);
		}
		if(n.left != null){
			int left_sum = curr_sum;
			printAll_adv(n.left,sum,left_sum,ll,head);			
		}
		
		if(n.right != null){
			int rght_sum = curr_sum;
			printAll_adv(n.right,sum,rght_sum,ll,head);
		}		
		ll.removeLast();
	}

how about this ! For inclusion of root..

void sum(Node * node, int sum){

k=k+node->value;
if(sum==k)
then store the node;

sum(node->left);
sum(node->right);
}

By this way we can compute all the destination nodes that sum upto the value and hence we can compute their paths..

void sum(Node *node, int sum) {
int ndata = node->data;
if(node == null && sum ==0){
return true;
}
if(sum(node->left, sum - ndata) == true || sum(node->right, sum - ndata) == true) {
printf("%s", ndata);
}else{
return false;
}
Above code will search for sum upto leaf paths
below will get paths if it finds sum in between any of nodes
void sum(Node *node, int sum) {
int ndata = node->data;
if(sum ==0){
return true;
}
if(sum(node->left, sum - ndata) == true || sum(node->right, sum - ndata) == true) {
printf("%s", ndata);
}else{
return false;
}