## Microsoft Yahoo Interview Question for Software Engineer / Developers

• 3

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

void printPaths(struct node* node) {
int path;

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

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

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.

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

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

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

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.

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

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;

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

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

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.

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

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

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

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

int temp = sum;
for(int i = level; i>=0;i--)
{
temp = temp - buffer[i];
if(temp==0)
print(buffer, level, i);
}
}

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

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

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

{
}

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

Also while calling findsum on head->left and head->right you cannot use the same buffer! for example consider level 2. buffer(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!

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.

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

void printPaths(struct node* node) {
int path;

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

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

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

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

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

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

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

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

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.

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;

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

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

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

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

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

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.

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

your input is even not a bst

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

True we are talking about BST rember the invariant

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 ?

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

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.

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)

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

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

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.

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

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

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

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

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

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.

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())
}
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);
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())
{
continue;
}

path.insertRight(node);
if(path.getCount() == value)
path.setCompleted(true);

}
}
if(rightPaths != null)
{
for(Path path:rightPaths)
{
path = (Path)path.clone();
if(path.isComplete())
{
continue;
}

path.insertLeft(node);
if(path.getCount() == value)
path.setCompleted(true);
}
}

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

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>();
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)
{
count += node.getValue();
}

public void insertRight(Node node)
{
count += node.getValue();
}

public int getCount()
{
return this.count;
}

public Object clone()
{
Path clone = new Path();
//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.count += rightPath.getCount();
return newPath;
}

}``````

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.

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

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.

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

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; // 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() {
}``````

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

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;

{

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

{
}
else
{
while(NULL != current->next)
current = current->next;
current->next = newNode;
}
}
{
return NULL;
else
{
}
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;

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

{
hasSum(temp->cell);
if(temp->cell->left != NULL)
{
}
if(temp->cell->right != NULL)
{
}
}
}
void hasSum(Node *root)
{
int path;
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);
}
}``````

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;
tempVec.erase(tempVec.begin());
}
else
sum = num;
}
}

if(sum==0)
{
if(tempVec.size()>1)
{
resVec.push_back(tempVec);
sum+= tempVec;
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;
}``````

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

>>

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;
}
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) {
}
if (top.right != null) {
}
}
}
}

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

}``````

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

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;
..int.l.=.100;
..find_sum(root,.sum,.a,.0);
..cout.<<."\n";
..traverse_sum(root->left,.sum);
..traverse_sum(root->right,.sum);
}

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.

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;
tempStart++;

}

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

if(root.data > remains)
return;

end = end + 1;
remains = remains - 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``````

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.

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

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

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.

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

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.

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

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

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.

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

}``````

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

}

}

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

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

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

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

}``````

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

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

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

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

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``````

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

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

if (root == null){
return;

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

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

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

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;

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

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;

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

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

``````//Simpler recursive version

static void printAllPathsSumToValue(Node root, int targetSum){
if(root == null) return;

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

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

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.

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