{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Path Sum – Solution & Complexity

Interview solutions
/
Path Sum

Solution Walkthrough

1. Recognize the Pattern

The key pattern is: root-to-leaf DFS that carries a running remaining-sum down the tree instead of accumulating a total up. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(n) — every node is visited at most once. Space: O(h) for the recursion stack, where h is the tree height (O(n) worst case on a skewed tree).

All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.

def has_path_sum(root: TreeNode, target_sum: int) -> bool:
    if root is None:
        return False

    if root.left is None and root.right is None:
        return root.val == target_sum

    remaining = target_sum - root.val
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

FAQ

See also

Practice Path Sum online (run code in the browser)Diameter of Binary Tree solution (easy)Invert Binary Tree solution (easy)Maximum Depth of Binary Tree solution (easy)Merge Two Binary Trees solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?