2018-01-17 10:15:00 UTC
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Given the below binary tree and sum = 22,
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Return 0 / 1 ( 0 for false, 1 for true ) for this problem
This problem is a variant of DFS where we are searching if the path from the root to leaf ends up with a given sum.
Base case would be if the root is null -> return 0 and if the root has no left and right child and its value is equal to the given sum -> return 1 (The check for left and right nil makes sure the search doesn't stop in the middle if the sum is met. We need the path to end at leaf node).
Otherwise, recursively check for the sum-root.data value on the left and right subtrees. At the end, if it's a leaf node and its value is equal to the net value, return true else return false. Let's see it in action:
def hasPathSum(a, b) return 0 if !a return 1 if (a.data == b) and !a.left and !a.right if ((a.left and hasPathSum(a.left, b-a.data) == 1) or (a.right and hasPathSum(a.right, b-a.data) == 1)) return 1 else return 0 end end
Owned & Maintained by Saurav Prakash
If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)