10.6 done and test fixed

gardncl · gardncl · commit a81bbd4aa02a · 2017-05-24T19:47:34.000-04:00
diff --git a/binarytrees/README.md b/binarytrees/README.md
@@ -5,7 +5,7 @@
 - [x] 10.3 ComputeLowestCommonAncestor
 - [x] 10.4 ComputeLCAWithParent
 - [x] 10.5 SumRootToLeaf
-- [ ] 10.6 FindRootToLeafSum
+- [x] 10.6 FindRootToLeafSum
 - [ ] 10.7 InorderIterative
 - [ ] 10.8 PreorderIterative
 - [ ] 10.9 ComputeKthNodeInorder
diff --git a/binarytrees/src/main/java/FindRootToLeafSum.java b/binarytrees/src/main/java/FindRootToLeafSum.java
@@ -4,9 +4,20 @@ public class FindRootToLeafSum {
     10.6
     */
 
-    public static boolean hasPathSum(BinaryTree<Integer> tree, int targetSum) {
+    public static boolean hasPathSum(BinaryTree<Integer> tree, Integer targetSum) {
+        return exists(tree, targetSum, 0);
+    }
+
+    private static boolean exists(BinaryTree<Integer> node, Integer targetSum, Integer count) {
+        if (node == null)
+            return false;
+
+        int current = node.data + count;
+        if (node.left == null && node.right == null)
+            return targetSum.equals(current);
 
-        return false;
+        return exists(node.left, targetSum, current) ||
+                exists(node.right, targetSum, current);
     }
 
 }
diff --git a/binarytrees/src/test/java/FindRootToLeafSumTest.java b/binarytrees/src/test/java/FindRootToLeafSumTest.java
@@ -12,7 +12,7 @@ public class FindRootToLeafSumTest {
     public void hasPathSum1() throws Exception {
         expected = true;
         tree = BinaryTreeUtil.getFullTree();
-        targetSum = 10;
+        targetSum = 7;
 
         test(expected, tree, targetSum);
     }
@@ -30,7 +30,7 @@ public void hasPathSum2() throws Exception {
     public void hasPathSum3() throws Exception {
         expected = true;
         tree = BinaryTreeUtil.getFigureTenDotOne();
-        targetSum = 519;
+        targetSum = 1365;
 
         test(expected, tree, targetSum);
     }
@@ -39,7 +39,7 @@ public void hasPathSum3() throws Exception {
     public void hasPathSum4() throws Exception {
         expected = false;
         tree = BinaryTreeUtil.getFigureTenDotOne();
-        targetSum = 591;
+        targetSum = 724;
 
         test(expected, tree, targetSum);
     }
