Root-to-Leaf Path Sum | Dataford Interview Questions

RealSelf can model hierarchical review or moderation data as a binary tree of integer scores. Given the root of a binary tree and an integer k, determine whether any path from the root to a leaf has values that sum exactly to k.

A node is a leaf when it has no left or right child. The path must begin at the root and end at a leaf, so stopping at an internal node does not count.

Formal Specification

Implement has_path_sum(root, k).

root is either None or a TreeNode with an integer val and optional left and right children.
k is an integer target sum.
Return True if at least one root-to-leaf path sums to k; otherwise return False.
Node values may be negative, zero, or positive.

For test cases, trees are represented as nested objects with val, left, and right fields, where a missing child is null.

Constraints

0 <= number of nodes <= 10^4
-10^9 <= node.val <= 10^9
-10^9 <= k <= 10^9
The input is a valid binary tree
A missing tree is represented by root = None

Function Signature

def has_path_sum(root, k):

Your question is Root-to-Leaf Path Sum. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem