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:!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! (please ue 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

class Node {
   int data;
   Node left, right;

   Node(int item) {
       data = item;
       left = right = null;
   }
}

public class BinaryTree {

   Node root;

   boolean haspathSum(Node node, int sum) {
       if (node == null)
           return (sum == 0);
       else {
           boolean ans = false;

           /* otherwise check both subtrees */
           int subsum = sum - node.data;
           if (subsum == 0 && node.left == null && node.right == null)
               return true;
           if (node.left != null)
               ans = ans || haspathSum(node.left, subsum);
           if (node.right != null)
               ans = ans || haspathSum(node.right, subsum);
           return ans;
       }
   }

   int checkIfpathExistsWithSum(Node node, int sum) {
       boolean res = haspathSum(node, sum);
       return res ? 1 : 0;

   }

   public static void main(String args[]) {
       int sum = 21;
       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);

       if (tree.checkIfpathExistsWithSum(tree.root, sum) == 1)
           System.out.println("There is a root to leaf path with sum " + sum);
       else
           System.out.println("There is no root to leaf path with sum " + sum);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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