Root-leaf path with specified sum
Write a program which takes as input an integer and a binary tree with integer weights, and checks if there exists a leaf whose path weight equals the specified sum.
Solution
- Recursively compute sum as we visit the nodes
- When we find a leaf node check if the sum equals the specified sum
Code
def root_to_leaf_sum_check(root, sum)
partial_sum = 0
root_to_leaf_sum_check_helper(root, sum, partial_sum)
end
def root_to_leaf_sum_check_helper(root, specified_sum, partial_sum)
return false if root.nil?
partial_path_sum += root.data
# Leaf node
if root.left.nil? && root.right.nil?
return partial_sum == specified_sum
end
return root_to_leaf_sum_check_helper(root.left, specified_sum, partial_sum) ||
root_to_leaf_sum_check_helper(root.right, specified_sum, partial_sum)
end
Complexity
- Time: Essentially its pre-order traversal, so O(n)
- Space: O(h) in the order of the height of the tree.