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
4 answers
Try this, use overload:
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 to share
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 to share
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 to share