{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Path Sum – Solution & Complexity

Interview solutions
/
Path Sum

Solution Walkthrough

  1. Step 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. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?