CareerCup

please check if dis works or not

bool hasPathSum(struct node* node, int sum)
{
/* return true if we run out of tree and sum==0 */
if (node == NULL)
{
return(sum == 0);
}
else
{

int subSum = sum - node->data;

return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right,subSum)||
hasPathSum(node->right,sum)||
hasPathSum(node->left, sum));
}
}

a solution using additional space: i.e., traverse the tree in pre-order
and keep the partial sums in a hash

after traversing left and right children, merge the hashes into one as well as add the value
of a root node to the hash, return it

here the required additional space is O(n) where n is the number of nodes in the tree
since we do not need to store all partial sums in a hash

well, hash is needed just to avoid duplicates, a simple array should also work

bool has_sum(node *t, hash& h) {
    if(t == 0)
        return false;
    if(t->value == sum)
        return true;
    hash h_l, h_r;
    if(has_sum(t->left, h_l))
        return true;
    if(has_sum(t->right, h_r))
        return true;
    h.add(t->value);
    forall x in h_l do
        x += t->value;
        if(x == sum)
            return true;
        h.add(x)
    }
    forall x in h_r do
        x += t->value;
        if(x == sum)
            return true;
        h.add(x)
    }
    return false; // no found yet
}
hash h;
has_sum(root, h)

This is working as awesome. try it.
// root is pointer to tree's root and sum_path is total you want to find.

bool print_sum_path(struct tree_node * root, int sum_path)
{
	if(sum_path == 0 && root == NULL)  {
		printf("()<-");
		return true;
	}
	else if(sum_path < 0) {
		return false;
	}
	else if (root == NULL) {
		return false;
	}
	else if (print_sum_path(root->refer[LEFT_CHILD],(sum_path - root->data))
			|| print_sum_path(root->refer[RGHT_CHILD],(sum_path - root->data))){
		printf("%d<-", root->data);
		return true;
	}
	else {
		return false;
	}
}

it is a DP problem. at each node, in addition to being a part of the parent node search path, a new search path also need to be started.

O(N^2) solution is possible

This should work, only issue is memory trace big. It uses a helper function pathSum which returns a list if a path exist with given sum, else null. Code is in Java.

//Get Path Sum if exist from given node
	private ArrayList<Node> pathSum(Node r, int sum, ArrayList<Node> l){
		ArrayList<Node> list;
		if(r == null){
			return null;
		}
		else if(r.data == sum){
			list = new ArrayList<Node>(l);
			list.add(r);
			return l;
		}else{
			list =new ArrayList<Node>(l);
			list.add(r);
			if(pathSum(r.left, sum - r.data, list) !=null)
				return list;
			if(pathSum(r.left, sum -r.data, list)!=null)
				return list;
			else
				return null;
		}	
	}
	
	//Check if given Path Sum exist any where in tree
	private ArrayList<Node> pathSumExist(Node r, int sum, ArrayList<Node> l){
		ArrayList<Node> list;
		if(r == null)
			return null;
		else if ( (l= pathSum(r, sum, l)) != null)
			return l;
		else{
			if ( (l= pathSum(r.left, sum, l)) != null)
				return l;
			if ( (l= pathSum(r.right, sum, l)) != null)
				return l;
			else 
				return null;
		}
	}

A small deviation to DFS is required and each Tree node will contain information about the summation of all of its previous root nodes.( an array containing sum of all node following from its top root). Eg. In below example node 2 will have an array containing( 2( self),9( self + 7) ,14( self+7+5))
5
/ \
7 6
/ \ /\
2 -3 5 1
Once we have this information then checking sum at each node and equating it against X will return result.

Java Function:
private static boolean depthFirstSearch(Tree root, int sum) {
boolean containsSum = false;
Stack<Tree> NV = new Stack<Tree>();
NV.push(root);
root.SumTillThisNode.add(root.Value);
while(!NV.empty())
{
Tree elem = NV.pop();
if( elem.containsSum(sum))
{
containsSum = true;
break;
}
else
{
if(elem.Left != null)
{
elem.Right.SumTillThisNode.add(elem.Left.Value);
elem.Left.SumTillThisNode.addAll(elem.SumTillThisNode);
NV.push(elem.Left);
}
if(elem.Right != null)
{
elem.Right.SumTillThisNode.add(elem.Right.Value);
elem.Right.SumTillThisNode.addAll(elem.SumTillThisNode);
NV.push(elem.Right);
}
}
}

return containsSum;
}

Small correction Above :
Earlier:
if(elem.Left != null)
{
elem.Right.SumTillThisNode.add(elem.Left.Value);

It should be:
if(elem.Left != null)
{
elem.Left.SumTillThisNode.add(elem.Left.Value);

int sum_sub_path(Node n,int sum,int original)
{
if(n==NULL) return 0;
cout<<n->v<<" "<<sum<<" "<<original<<"\n";
if(n->v == sum) return 1;


if(n->v > sum)
{
if(original < mytempnode->v)
if(sum_sub_path(mytempnode->l,original,original)> 0)
return 1;
else
if(sum_sub_path(mytempnode->r,original,original)> 0)
return 1;

}
else
{
if( (sum - n->v) < n->v)
{
if(sum_sub_path(n->l,sum - n->v,original) > 0)
return 1;
}
else
{
if(sum_sub_path(n->r,sum- n->v,original) > 0)
return 1;
}
}
}
set mytempnode=root initially and sum=original to initial sum.
This is working O(nlog n) code with no extra space (except system stack).

<pre lang="" line="1" title="CodeMonkey21595" class="run-this">class TreeNode {

public TreeNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
private int data;
private TreeNode left;
private TreeNode right;
}
class SumFromRoot {
/**
*
* @param root, the tree root.
* @param remainingSum, the remaining sum to be found
* @param originalSum, the original sum we were looking for
*
* @return true if sum is 0 or sum is found.
*/
public boolean hasSum(TreeNode root, int remainingSum, int originalSum) {
if(root == null) {
return remainingSum == 0;
} else if(remainingSum == 0) {
return true;
} else {
if(remainingSum - root.getData() == 0) {
return true;
}
return hasSum(root.getLeft(), originalSum, originalSum) ||
hasSum(root.getLeft(), remainingSum - root.getData(), originalSum) ||
hasSum(root.getRight(), originalSum, originalSum) ||
hasSum(root.getRight(), remainingSum - root.getData(), originalSum);
}
}

/**
* 1
* / \
* 2 -3
* /
* 4
*/
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.setData(1);
root.setLeft(new TreeNode(2));
root.setRight(new TreeNode(-3));
root.getLeft().setLeft(new TreeNode(4));
SumFromRoot instance = new SumFromRoot();
for(int i = -3; i < 9; ++i) {
System.out.print(i);
System.out.print(' ');
System.out.println(String.valueOf(instance.hasSum(root, i, i)));
}
}
}
</pre><pre title="CodeMonkey21595" input="yes">
</pre>

1) serialize the tree [ into deque ] using any traversal
2) Find all the combinations that equals T(given value) [ Same as finding all sum equal in an array] and push it in to vector of vectors.
3) Read each vector
Do level wise traversal of the tree and arrange the values in appropriate order
now check if the adjacent node is left or right node of the previous
if yes add this path into the result set.