Commit a0bbacf

@@ -1,5 +1,7 @@
 <<-DOC
-Given a binary tree t and an integer s, determine whether there is a root to leaf path in t such that the sum of vertex values equals s.
+Given a binary tree t and an integer s,
+determine whether there is a root to leaf path in t
+such that the sum of vertex values equals s.
 
 Example
 
@@ -131,7 +133,8 @@ Guaranteed constraints:
 
 [output] boolean
 
-Return true if there is a path from root to leaf in t such that the sum of node values in it is equal to s, otherwise return false.
+Return true if there is a path from root to leaf in t such that the sum of node values in it is equal to s,
+otherwise return false.
 DOC
 
 describe "#path_with_given_sum?" do
@@ -154,6 +157,15 @@ describe "#path_with_given_sum?" do
     sum == target_sum
   end
 
+  def path_with_given_sum?(tree, target)
+    return target.zero? if tree.nil?
+    new_target = target - tree.value
+    return new_target.zero? if leaf?(tree)
+    return true if tree.left && path_with_given_sum?(tree.left, new_target)
+    return true if tree.right && path_with_given_sum?(tree.right, new_target)
+    false
+  end
+
   [
     { t: { "value": 4, "left": { "value": 1, "left": { "value": -2, "left": nil, "right": { "value": 3, "left": nil, "right": nil } }, "right": nil }, "right": { "value": 3, "left": { "value": 1, "left": nil, "right": nil }, "right": { "value": 2, "left": { "value": -2, "left": nil, "right": nil }, "right": { "value": -3, "left": nil, "right": nil } } } }, s: 7, x: true },
     { t: { "value": 4, "left": { "value": 1, "left": { "value": -2, "left": nil, "right": { "value": 3, "left": nil, "right": nil } }, "right": nil }, "right": { "value": 3, "left": { "value": 1, "left": nil, "right": nil }, "right": { "value": 2, "left": { "value": -4, "left": nil, "right": nil }, "right": { "value": -3, "left": nil, "right": nil } } } }, s: 7, x: false },
@@ -179,6 +191,10 @@ describe "#path_with_given_sum?" do
       @right = right
     end
 
+    def to_h
+      { value: value, left: left&.to_h, right: right&.to_h }
+    end
+
     def self.build_from(hash)
       return nil if hash.nil?
       Tree.new(hash[:value], left: build_from(hash[:left]), right: build_from(hash[:right]))