Write a method that returns 1 if there is a root-to-leaf path whose node values

Question

Write a method that returns 1 if there is a root-to-leaf path whose node values sum to target and returns 0 if there is no such root-to-leaf path.

For example, in the tree below there are exactly four root-to-leaf paths. The sums on these paths are 27, 22, 26, 18, so hasPathSum(22,tree) will return 1 for the tree shown and hasPathSum(32,tree) will return 0 for the tree shown.

Note that an empty tree will always return 0, regardless of the value oftarget. Similarly, a tree with exactly one node will result in returning 1 if target is the value in the node, and zero otherwise.

The TreeNode class will be accessible when your method is tested.

public class TreeNode { int info;

TreeNode left;

TreeNode right;

TreeNode(int x){

info = x;

}

TreeNode(int x, TreeNode lNode, TreeNode rNode)

{ info = x; left = lNode; right = rNode; } }

skeleton code is provided below:

public class PathSum {

public int hasPath(int target TreeNode tree){

// replace with working code

return 0; } }

Examples:

Returns 1, there is a path whose sum is target

Returns 0, there is no path that sums to 5

Returns 1, this is the tree diagrammed above

Explanation / Answer

// Note: Please give thumbs up if you like the answer

class Node
{
int data;
Node left, right;
  
Node(int item)
{
data = item;
left = right = null;
}
}
  
class BinaryTree
{
Node root;
int found=0;
  
int calcSumPath(int target, int ints[], int len)
{
int i;
int sum = 0;
for (i = 0; i < len; i++)
{
//System.out.print(ints[i] + " ");
sum = sum + ints[i];
}
//System.out.println("");
//System.out.println("Sum of path is: "+sum);
if(sum==target)
{
   //System.out.println("Found the target value: "+target);
   return 1;
}
else
{
   //System.out.println("Unable to find the target value: "+target);
   return 0;
}
}
  
int hasPathSumRecur(int target, Node node, int path[], int pathLen)
{
if (node == null)
return 0;

path[pathLen] = node.data;
pathLen++;

if (node.left == null && node.right == null)
{
   if(calcSumPath(target, path, pathLen)==1)
   {
       found=1;
       return 1;
   }
}
else
{
   if(found !=1)
   {
       hasPathSumRecur(target, node.left, path, pathLen);
       hasPathSumRecur(target, node.right, path, pathLen);
   }
}
  
return 0;
}
  
  
int hasPathSum(int target, Node node)
{
   int path[] = new int[1000];
   found=0;
   hasPathSumRecur(target, node, path, 0);
   if(found==1)
   {
   return 1;
   }
   else
   {
       return 0;
   }
}
  
// 10
// /
// 8 2
// / /
// 3 5 2
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(2);
//tree.printPaths(23, tree.root);
//tree.printPaths(18, tree.root);
int checkRet;
checkRet= tree.hasPathSum(23, tree.root);
  
if(checkRet==1)
   System.out.println("There is a path whose sum is target 23");
else
   System.out.println("No path exist whose sum is target 23");

checkRet = tree.hasPathSum(18, tree.root);
if(checkRet==1)
   System.out.println("There is a path whose sum is target 18");
else
   System.out.println("No path exist whose sum is target 18");
  
checkRet = tree.hasPathSum(21, tree.root);
if(checkRet==1)
   System.out.println("There is a path whose sum is target 21");
else
   System.out.println("No path exist whose sum is target 21");
  
checkRet = tree.hasPathSum(14, tree.root);
if(checkRet==1)
   System.out.println("There is a path whose sum is target 14");
else
   System.out.println("No path exist whose sum is target 14");
  
checkRet = tree.hasPathSum(15, tree.root);
if(checkRet==1)
   System.out.println("There is a path whose sum is target 15");
else
   System.out.println("No path exist whose sum is target 15");

}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.