Path Sum

Problem statement

Given a binary tree and an integer targetSum, return whether there is a root-to-leaf path whose values add up to targetSum.

Example:

Input:

root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22

Expected output:

true

Why: one valid path is 5 → 4 → 11 → 2.

Practice on LeetCode: Path Sum

Golang Solution

Walk down, subtracting each node’s value from the remaining target. Only a leaf can finish the path — if the remainder is 0 there, return true; otherwise try left or right.

Time: O(n) — each node visited at most once
Space: O(h) — recursion stack

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    targetSum -= root.Val

    // We only have a valid path if we're at a leaf
    if root.Left == nil && root.Right == nil {
        return targetSum == 0
    }

    return hasPathSum(root.Left, targetSum) ||
           hasPathSum(root.Right, targetSum)
}