# Path to a sheet that has a specific sum in a binary tree

I know how to find if a binary tree has a specific path with a given sum (if this is not the best way, please let me know):

``````int pathSum(MyNode root, int sum)
{
if(root == null)
return -1;
int temp = sum - root.value;
return(pathSum(root.left,temp) || pathSum(root.right,temp));
}
```

```

I cannot figure out how to print a specific path.

My Node class looks like this:

``````class MyNode {
int value;
MyNode left;
MyNode right;

MyNode(int value)
{
this.value = value;
}
}
```

```
+3

source to share

`````` public void pathToSum(int sum) {
pathToSum(root, sum);
}

private boolean pathToSum(Node n, int sum) {
if (null != n) {
sum -= n.data;
boolean found = pathToSum(n.left, sum);

if (!found) {
found = pathtoSum(n.right, sum);
}
if (found) {
println(n.data);
return found;
}
}
return 0 == sum ? true : false;
}
```

```

This code is tested with the following classes:

``````import java.util.LinkedList;
import java.util.Queue;
public class BST {
Node root;
public BST(){
root = null;
}

public void insert(int el){

Node tmp = root, p=null;
while(null!=tmp && el != tmp.data){
p=tmp;
if(el<tmp.data)
tmp=tmp.left;
else
tmp=tmp.right;
}
if(tmp == null){
if(null == p)
root = new Node(el);
else if(el <p.data)
p.left= new Node(el);
else
p.right=new Node(el);
}
}//

public void pathToSum(int sum) {
pathToSum(root, sum);
}//

private boolean pathToSum(Node n, int sum) {
if (null != n) {
sum -= n.data;
boolean found = pathToSum(n.left, sum);

if (!found) {
found = pathToSum(n.right, sum);
}
if (found) {
System.out.println(n.data);
return found;
}
}
return 0 == sum ? true : false;
}

public static void main(String[] args){
int[] input={50,25,75,10,35,60,100,5,20,30,45,55,70,90,102};
BST bst = new BST();
for(int i:input)
bst.insert(i);
bst.pathToSum(155);
}
}

class Node{
public int data;
public Node left;
public Node right;
public Node(int el){
data = el;
}
}
```

```

Result:

``````45
35
25
50
```

```
+4

source

I suggest changing the MyNode class to include the parent node:

``````MyNode left;
MyNode right;
MyNode parent;

MyNode(int value, MyNode parent)
{
this.value = value;
this.parent = parent;
}
```

```

and then when you hit a node with the correct amount, you can pass that node to another function that follows the pedigree path until it hits a node with a null parent (root).

+1

source

Nice puzzle, I liked it. You almost had it, just some confusion about int vs boolean rather than checking the end condition of the sum to be zero.

``````public class NodeSums {

static boolean pathSum(MyNode root, int sum) {
boolean ret;
if (root == null) {
ret = sum == 0;
} else {
int remain = sum - root.value;
ret = pathSum(root.left,remain) || pathSum(root.right, remain);
}
return ret;
}

static class MyNode {
int value;
MyNode left;
MyNode right;

MyNode(int value) {
this.value = value;
}
}

public static void main(String[] args) {

/**
* Valid sums will be 3, 8, and 9
*
*    1 -- 2
*      --
*      -- 3 -- 4
*           --
*           -- 5
*/
MyNode root = new MyNode(1);
root.left = new MyNode(2);
root.right = new MyNode(3);
root.right.left = new MyNode(4);
root.right.right = new MyNode(5);

for (int i = 1; i < 10; i++) {
System.out.println("Path sum " + i + " " + pathSum(root, i));
}
}
}
```

```

Output

``````Path sum 1 false
Path sum 2 false
Path sum 3 true
Path sum 4 false
Path sum 5 false
Path sum 6 false
Path sum 7 false
Path sum 8 true
Path sum 9 true
```

```
+1

source

If you store the parent of each node in MyNode, you can find the (backward) path from the root to any node by getting the parent in a loop until it is zero.

Also, your code for pathSum seems to mix booleans and ints, and you never check the value of sum.

0

source

All Articles