Microsoft Yahoo Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}

- dingxiang April 24, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi dingxiang,

The solution you gave just print out all the paths from root to leaf. You should keep track of the sum and check it before you print out the path.

- vodangkhoa April 24, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 similarly 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)

- Anonymous April 30, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

With these types of questions, paths in binary-trees, there is almost always some confusion about what is meant by a 'path' in a binary tree. A path in a binary-tree is the sequence of edges between any two of its nodes, not just the path from the root to the leaves, which is just the height. By definition a tree is an undirected graph with 'simple paths' between any two of its nodes. A 'simple path' is a path which is a sequence of edges that doesn't use the same edge more than once. See ‘Discrete Mathematic and its Applications’ by Rosen pp 528-529.

- Michael June 22, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I forgot to put

and

and so indentation is bad. I'm retrying again:

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)

- Anonymous April 30, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}

- dingxiang May 09, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need two more recursive calls to printPathsRecur where you don't subtract the sum. Something like this.

else {
printPathsRecur(node->left, path, pathLen, sum-node->left.data);
printPathsRecur(node->right, path, pathLen, sum-node->right.data);

printPathsRecur(node->left, path, pathLen, ORIGINAL_SUM);
printPathsRecur(node->right, path, pathLen, ORIGINAL_SUM);
}
ORIGINAL_SUM is the sum that was passed in at the beginning.

- vodangkhoa May 10, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

last two recursive calls
printPathsRecur(node->left, path, pathLen, ORIGINAL_SUM);
printPathsRecur(node->right, path, pathLen, ORIGINAL_SUM);
will be called many(no of ancester+1) times for the same node

- Ravi Kant Pandey June 12, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}
}

- Den May 23, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

theres a type o , it should be level+1 and not left +1;

{
findsum(head->left, sum, buffer, level+1);
findsum(head->right, sum, buffer, level+1);
}

- jj August 22, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also while calling findsum on head->left and head->right you cannot use the same buffer! for example consider level 2. buffer[1](consider this represents data in level 2) will have different values for the left node and the right node. Hence you should create a new array with the same copies and call the recursion.

But this uses a lot of memory!

- kairav January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous May 28, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}

- av June 26, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- @mit July 01, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will not print the full path as root will be pointing to the last node which is making the sum....

and even if u are taking the main root of the tree then also it will only print the nodes which are starting from root ...

ur solution is little bit wrong ..

- ardhvaryu June 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- @mit July 01, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi @mit,

I think your code is correct except the print routine. It should be :


void printPath(Node root,int sum)

if(root->key==sum)
               printf(" %d ",root->key);
      
       else
          printPath(root->parent,sum-root->key);
          printf(" %d ",root->key);
   
       return;

- TheGreatOne September 02, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

So I think this could work but the complexity of this little high...
say there are n nodes in the tree and log(n) is the height of the tree...then the leaf node would be checked log(n) times, the one above it for log(n)-1 times and so on...it could tend towards a log(n)!...while for large values of n, will perform badly.

- Ram September 30, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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");
}

- tujl July 02, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

- Anonymous July 02, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }

- Gabbar July 29, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AT August 24, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Tangent August 25, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- KDACE October 18, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your input is even not a bst

- Anonymous October 21, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

True we are talking about BST rember the invariant

- Anonymous February 08, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

- Vel October 27, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i can think of an O(n) soln but the space complexity is O(n^2). Here's how- keep adding every new element to a new list as well as to existing list. so for example you traverse 1,2,3 you'll have 3 lists:

1 2 3
2 3
3

also keep a count of the running sum of each list. if it equals or goes beyond your target stop adding to that list.


as for finding a subsequence of given sum in an array of integers (+ve and -ve), you can repeat the above algorithm in that case too.

- joe di maggio October 29, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Nickname November 03, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no in dfs it will start from root only(BST) so it will not give the cases when the path is via root and not originating from it or even not including it

- Anonymous August 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Chow Yun Fat November 03, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nar November 06, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

- Anonymous November 28, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

- Vamsi November 28, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Anonymous January 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Eric Cartman January 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Nikhil Agashe January 14, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
		}

	}

- vairaghi January 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- dawninghu February 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Swati February 06, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- Anish April 17, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

brilliant idea, Anish ;)
looks like it really works: indeed one needs only one pass over the tree structure to find all
sums. Implementation is a bit quick-and-dirty but I hope quite understandable:

struct node {
    int val;
    node *left;
    node *right;
};

int A[20][20]; // A[i][j] stores sum of path from level i to level j

int sum = 12; // the sum we are looking for 

// j is the current level
void traverse(node *t, int j) {

    if(t == 0)
        return;
    
    if(t->val == sum)
        printf("%d\n", sum);
    A[j][j] = t->val;

    for(int i = 0; i < j; i++) {
        A[i][j] = A[i][j-1] + t->val;
        
        if(A[i][j] == sum) {
            for(int k = j; k >= i; k--) {
                int tmp = A[i][k];
                if(k > i)
                    tmp -= A[i][k-1];
                printf("%d ", tmp);
            }
            printf("\n");
        } 
    }
    traverse(t->left, j+1);
    traverse(t->right, j+1);
}

main() {
  traverse(head, 0);
}

- pavel.em June 16, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- creepingdog April 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
	}
}

- algooz April 27, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous May 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

>>

- XYZ September 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}

}

- Laks September 23, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- winia October 31, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- nchikkam December 30, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Dumbo February 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous February 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- susanta July 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But how you are getting nlogn... It sould be O(n)*O(n/2)*O(n/2) == O(n^3).
first O(n) --> as we travelling to each node for checking right subtree and left subtree
O(n/2) == checking each subtree on the right and left of a node

- SG ... May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think most guys have forgot to optimize it. Consider this. Suppose I have to sum up to 20 and the current node value is 10. Then I can simply ignore the entire right subtree because and value 'X' in the right subtree must be greater than 10 and hence 10 + X > 20. So the solution will not include any node form right sub tree. This concept can be applied recursively and will greatly reduce the overall time.

- chandransuraj March 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Numbers can be negative. Also, there can be a path starting somewhere in the subtree that sums to the value you want. For this problem you must always do an extensive search.

- Sia July 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I DONT KNOW WHAT YOU ALL PEOPLE UNDERSTOOD BY THE question but i thought the question was to print the any path that may have sum ..

10
/ \
5 11
/ \
4 6
/
2

in this find path which sum 17
answer should be 2 4 5 6 but i guess all the above codes will not be able to find this one ...

- AT ALL ABOVE June 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

2 4 5 6 is not a valid 'path' in a 'typical' binary tree since binary trees only have paths that go from parent to child. so 5 4 2 is a valid path, and you cannot include 6.

- Sia July 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks like my solution is correct.

import java.util.Stack;

public class BinarySearchTree {

	private class Node {
		int data;
		Node left;
		Node right;
		Node(int v, Node left, Node right){
			data = v;
			this.left = left;
			this.right = right;
		}		
	}

	public Node root;

	public void insertNode(int data) {
		if (root == null) {
			root = new Node(data, null, null);			
			return;
		}
		Node cur = root;
		do {
			if(data >= cur.data) {
				if(cur.right != null) cur = cur.right;
				else {
					cur.right = new Node(data, null, null);
					return;
				}
			}else {
				if(cur.left != null) cur = cur.left;
				else {
					cur.left = new Node(data, null, null);
					return;
				}
			}
		}while(cur != null);
	}

	public void inorder() {
		System.out.println("\nin-order :");
		printSubTreeInOrder(root);
	}
	
	public void preorder() {
		System.out.println("\npre-order :");
		printSubTreePreOrder(root);
	}
	
	private void printSubTreeInOrder(Node p){
		if(p.left != null) printSubTreeInOrder(p.left);
		System.out.print("\t" + p.data);
		if(p.right != null) printSubTreeInOrder(p.right);
	}
	private void printSubTreePreOrder(Node p){
		System.out.print("\t" + p.data);
		if(p.left != null) printSubTreePreOrder(p.left);		
		if(p.right != null) printSubTreePreOrder(p.right);
	}
	public void printAllPathWithSum(int sum){
		Stack<Node> path = new Stack<Node>();
		findPath(root, sum, path);
	}
	
	private void printPath(Stack<Node> path){
		System.out.print("\nFind Path:");
		for(Node n: path){
			System.out.print("\t" + n.data);
		}
	}
	
	private void findPath(Node p, int value, Stack<Node> path){
		if(p == null) return;
		if(p.data == value){
			path.push(p);
			printPath(path);
			path.pop();
		}else {
			path.push(p);
			if(p.left != null) findPath(p.left, value - p.data, path);
			if(p.right != null)findPath(p.right, value- p.data, path);
			path.pop();			
		}
		if(p.left != null) findPath(p.left, value , path);
		if(p.right != null)findPath(p.right, value, path);
	}

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

		BinarySearchTree tree = new BinarySearchTree();
		tree.insertNode(5);
		tree.insertNode(2);
		tree.insertNode(7);
		tree.insertNode(1);
		tree.insertNode(3);
		tree.insertNode(9);
		tree.inorder();
		tree.preorder();
		tree.printAllPathWithSum(1);
		tree.printAllPathWithSum(0);
		tree.printAllPathWithSum(16);
		tree.printAllPathWithSum(9);
	}

}

- Anonymous September 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This should work. DFS, when visiting each node follow up the parent and sum the numbers ant compare unitl you find a sum that equals the value. if the sum is greater then the value break out of the inner loop.

Additional optimizations can be added because the question asks for a binary search tree. meaning we can exclude parts of the tree from the DFS knowing that all the values in that portion of the tree will be larger than value.

void FindPaths(TreeNode root, int value)
{
if (root == null) return null;

Stack<TreeNode> stack = new Stack<TreeNode>();

stack.Push(root);

while (stack.Count > 0)
{
TreeNode cur = stack.Pop();

TreeNode Cur2 = cur;
int sum = 0;
string path = "";

while (Cur2 != null)
{
sum += Cur2.key;
Cur2 = Cur2.Parent;

path += Cur2.key + " ";

if (sum == value)
{
System.Console.WriteLine(path);
break;
}
else if (sum > value)
{
break;
}
}


if (cur.Left != null)
{
stack.Push(cur.Left);
}
if (cur.Right != null)
{
stack.Push(cur.Right);
}

}

}

- Anonymous September 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

could take out this optimization to allow for negative numbers.

else if (sum > value)
{
break;
}

As well as the break in the case above it

- Anonymous September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

static void FindPaths(TreeNode root, int value)
        {
            if (root == null) return;

            Stack<TreeNode> stack = new Stack<TreeNode>();

            stack.Push(root);

            while (stack.Count > 0)
            {
                TreeNode cur = stack.Pop();

                TreeNode Cur2 = cur;
                int sum = 0;
                string path = "";

                while (Cur2 != null)
                {
                    sum += Cur2.key;
                    
                    path += Cur2.key + " ";

                    if (sum == value)
                    {
                        System.Console.WriteLine(path);
                       
                    }
                   

                    Cur2 = Cur2.Parent;
                }
                

                if (cur.Left != null)
                {
                    stack.Push(cur.Left);
                }
                if (cur.Right != null)
                {
                    stack.Push(cur.Right);
                }

            }

- Anonymous September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think it should work

printf_path(node * ptr, curr_sum,Value)
  {
        if(curr_sum==Value)
        {  
                 //found a path
        }
        else
        {
             if(ptr->left->data+curr_sum<=Value)/*continuing adding sum from left*/
                   print_path(ptr->left,ptr->left->data+curr_sum,Value); 
               if(ptr->left->data<=Value)  /*new path starting from the current node*/
                   print_path(ptr->left,ptr->left->data,Value); 
               if(ptr->right->data+curr_sum<=Value) /*continuing adding sum from right*/
                   print_path(ptr->right,ptr->right->data+curr_sum,Value); 
                if(ptr->right->data+curr_sum<=Value) 
/*new path starting from current node*/
                   print_path(ptr->right,ptr->right->data,Value);
      }
  }

- monika.agarwal712 January 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how will u "print" that path?? can u please explain

- Joey August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Questions: does any node contain a negative value? If yes, then the cut off can not be done so easily. E.g. if the target sum is 5 and the tree is as follows:

Tree:         
                 5
              /   
            -1
                \
                 1

- wangpidong October 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public void allPathSum(BNode root,Stack<BNode> s){

if (root == null){
return;

}
s.add(root);
if (root.left == null && root.right == null){
int sum =0;
for (BNode node : s){
System.out.print(node.data+" + ");
sum =sum+node.data;
}
System.out.print(" = "+(sum)+" \n");


}

allPathSum(root.left,s);
allPathSum(root.right,s);
s.pop();

- Tony March 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/// How About Using Recursion Solution

struct Node
{
    int val;
    Node * left;
    Node * right;
    Node(int v = 0) : val(v), left(NULL), right(NULL)
    {   
    }   
};

int find_path_imp(Node * root, int val, vector<int> & one, vector< vector<int> > & res)
{
    if(0 == val) return 0;
    if(NULL == root) return 0;
    if(root->val < val) {
        vector<int> lone = one;
        lone.push_back(root->val);
        find_path_imp(root->left, val - root->val, lone, res);
        vector<int> rone = one;
        rone.push_back(root->val);
        find_path_imp(root->right, val - root->val, rone, res);
        return 0;
    }   
    else if(root->val == val) {one.push_back(root->val); res.push_back(one); one.pop_back(); return 0;} 
    else return 0;
}

int print_res(vector<int> & l, int v, vector<int> & r)
{
    for(int i = 0; i < l.size(); i ++) printf("%d ", l[i]);
    printf("%d ", v); 
    for(int i = 0; i < r.size(); i ++) printf("%d ", r[i]);
    printf("\n");

    return 0;
}
int find_path(Node * root, int val)
{
    if(NULL == root) return 0;
    if(root->val == val) {
        /// 1.0 result path include rootnode
        /// 2.0 result path just in left child
        printf("%d\n", root->val);
        find_path(root->left, val);
    }
    else if(root->val < val) {
        /// 1.0 result path include rootnode
        /// 2.0 result path just in left child
        /// 3.0 result path just in right child
        int left = val - root->val;
        vector<int> lone, rone;
        vector< vector<int> > lres, rres;
        for(int i = 0; i <= left; i ++) {
            lres.clear(); rres.clear();
            find_path_imp(root->left, i, lone, lres);
            find_path_imp(root->right, left - i, rone, rres);
            vector<int> empty;
            if(0 == i) lres.push_back(empty);
            if(left == i) rres.push_back(empty);
            for(int li = 0; li < lres.size(); li ++) {
                for(int ri = 0; ri < rres.size(); ri ++) {
                    print_res(lres[li], root->val, rres[ri]);
                }
            }
        }

        find_path(root->left, val);
        find_path(root->right, val);
    }
    else {
        /// 1.0 result path just in left child
        find_path(root->left, val);
    }

    return 0;
}

- zombie July 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean hasPathSum(int sum) { 
	 return( hasPathSum(root, sum) ); 
	}

	boolean hasPathSum(BTNode node, int sum) { 
	  // return true if we run out of nodes and sum==0 
	  if (node == null) { 
	    return(sum == 0); 
	  } 
	  else 
	  { 
		// otherwise check both subtrees 
		int subSum = sum - node.data; 
		return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum)); 
	  } 
	}

- GReeky February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

i think this will work
public void allPathSum(BNode root,Stack<BNode> s){

if (root == null){
return;

}
s.add(root);
if (root.left == null && root.right == null){
int sum =0;
for (BNode node : s){
System.out.print(node.data+" + ");
sum =sum+node.data;
}
System.out.print(" = "+(sum)+" \n");


}

allPathSum(root.left,s);
allPathSum(root.right,s);
s.pop();

- Tony March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AllPathsSumToValue {
	class Node {
		int value;
		Node leftChild, rightChild;
	}
	
	/**
	 * DFS on the tree, maintain sums upto current that start at every node in the stack
	 * @param root
	 * @param targetSum
	 */
	static void printAllPathsSumToValue(Node root, int targetSum){
		if(root == null) return;
		
		LinkedList<Node> currentPath = new LinkedList<Node>();
		
		// use a AVL tree / RB tree for faster lookup later
		Map<Node,Integer> pathSums = new HashMap<Node,Integer>();
		Map<Node,Integer> nodeHeight = new HashMap<Node, Integer>();
		
		currentPath.push(root);
		int currNodeValue = root.value;
		if(currNodeValue == targetSum){
			printPath(currentPath, root , 0);
		}
		pathSums.put(root, currNodeValue);
		nodeHeight.put(root, 0);
		
		while(!currentPath.isEmpty()){
			Node currNode = currentPath.peek();
			int currNodeHeight = nodeHeight.get(currNode);
			
			Node nextNode = null;
			int nextNodeHeight = currNodeHeight;
			if(currNode.leftChild != null){
				nextNode = currNode.leftChild;
				nextNodeHeight++;
			} else if(currNode.rightChild != null){
				nextNode = currNode.rightChild;
				nextNodeHeight++;
			} else {
				while(nextNode == null){
					currentPath.pop();
					pathSums.remove(currNode);
					nodeHeight.remove(currNode);
					
					if(currentPath.isEmpty()){
						break;
					}
					Node parentNode = currentPath.peek();
					if(currNode == parentNode.leftChild && parentNode.rightChild != null){
						nextNode = parentNode.rightChild;
					} else {
						pathSums.remove(currNode);
						currNodeValue = currNode.value;
						for(Node ancestor : pathSums.keySet()){
							int sumTillParentCurrNode = pathSums.get(ancestor);
							pathSums.put(ancestor, sumTillParentCurrNode-currNodeValue);
						}
						currNode = parentNode;
						nextNodeHeight--;
					}
				}
			}
			
			if(nextNode != null){
				currNode = nextNode;
				currentPath.push(currNode);
				nodeHeight.put(nextNode, nextNodeHeight);
				
				currNodeValue = currNode.value;
				for(Node ancestor : pathSums.keySet()){
					int sumTillParentCurrNode = pathSums.get(ancestor);
					if(sumTillParentCurrNode + currNodeValue == targetSum){
						printPath(currentPath, ancestor, nodeHeight.get(ancestor));
					}
				}
				pathSums.put(currNode, currNodeValue);
				if(currNodeValue == targetSum){
					printPath(currentPath, currNode, nodeHeight.get(currNode));
				}
			}

		}		
	}
	   
	static void printPath(LinkedList<Node> currentPath, Node startAncestor, int startAncestorHeight){
		for(int h = startAncestorHeight; h < currentPath.size(); h++){
			Node currNode = currentPath.get(h);
			System.out.print(currNode + "\t->\t");
		}
		System.out.println();
	}
}

- just_do_it July 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

//Simpler recursive version

static void printAllPathsSumToValue(Node root, int targetSum){
		if(root == null) return;
		
		LinkedList<Node> currentPath = new LinkedList<Node>();
		
		Map<Node,Integer> pathSums = new HashMap<Node,Integer>();
		Map<Node,Integer> nodeHeight = new HashMap<Node, Integer>();
		
		printAllPathsSumToValue(currentPath, root, targetSum, pathSums, nodeHeight, 0 );
	}
	
	static void printAllPathsSumToValue(LinkedList<Node> currentPath, Node currNode, int targetSum,
			Map<Node,Integer> pathSums, Map<Node,Integer> nodeHeight, int currNodeHeight){

		currentPath.push(currNode);
		int currNodeValue = currNode.value;
		
		pathSums.put(currNode, currNodeValue);
		nodeHeight.put(currNode, currNodeHeight);
		
		for(Node ancestor : pathSums.keySet()){
			int sumTillParentCurrNode = pathSums.get(ancestor);
			if(sumTillParentCurrNode + currNodeValue == targetSum){
				printPath(currentPath, ancestor, nodeHeight.get(ancestor));
			}
		}
		pathSums.put(currNode, currNodeValue);
		if(currNodeValue == targetSum){
			printPath(currentPath, currNode, nodeHeight.get(currNode));
		}
		
		if(currNode.leftChild != null){
			printAllPathsSumToValue(currentPath, currNode.leftChild, targetSum, pathSums, nodeHeight, currNodeHeight+1);
		}
		
		if(currNode.rightChild != null){
			printAllPathsSumToValue(currentPath, currNode.rightChild, targetSum, pathSums, nodeHeight, currNodeHeight+1);
		}
		
		currentPath.pop();
		pathSums.remove(currNode);
		nodeHeight.remove(currNode);
	}
	   
	static void printPath(LinkedList<Node> currentPath, Node startAncestor, int startAncestorHeight){
		for(int h = startAncestorHeight; h < currentPath.size(); h++){
			Node currNode = currentPath.get(h);
			System.out.print(currNode + "\t->\t");
		}
		System.out.println();
	}

- just_do_it July 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the main logic. Paths in T that that have sum S is

{Paths that start with T that sum have sum S} Union {Paths that start with T->left that have sum S } Union {Paths that start with T->right that have sum S} Union {T} X {Paths that start with T-> left that have sum S-T->value} Union {T} X {Paths that start with T->right that have sum S-T->value}

Below is a C++ 11 implementation:

typedef vector<vector<shared_ptr<TreeNode>>> path_list_type;
void FindPathsWithStartNode(shared_ptr<TreeNode> startNode, int v, path_list_type &output, vector<shared_ptr<TreeNode>> current_path) {
	if(!startNode) { 
		return;
	}
	current_path.push_back(startNode);
	if(startNode->value == v) {
		output.push_back(current_path);
	}
	FindPathsWithStartNode(startNode->left, v - startNode->value, output, current_path);
	FindPathsWithStartNode(startNode->right, v -  startNode->value, output, current_path);
	FindPathsWithStartNode(startNode->left, v, output, vector<shared_ptr<TreeNode>>());
	FindPathsWithStartNode(startNode->right, v, output, vector<shared_ptr<TreeNode>>());

}
path_list_type FindPaths(shared_ptr<TreeNode> t, int v) {
	path_list_type p;
	FindPathsWithStartNode(t, 4, p, vector<shared_ptr<TreeNode>>());
	return p;
}

- Mhret November 15, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More