Path Sum Solution Explained

Data Structures / Tree

Path Sum

Easy

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Example

Example 1:

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

Output: true

Explanation: The root-to-leaf path 5 → 4 → 11 → 2 sums to 22.



Example 2:

Input: root = [1,2,3], targetSum = 5

Output: false

Explanation: There are two root-to-leaf paths: 1 → 2 (sum=3) and 1 → 3 (sum=4). Neither equals 5.

Understanding the Problem

A root-to-leaf path is a path starting from the root node and ending at a leaf node (a node with no children). We need to find if any such path has values that sum to the target.

Key Observations

The path must start at root and end at a leaf (not just any node)
We subtract each node's value from targetSum as we traverse down
When we reach a leaf, we check if remaining sum equals the leaf's value
If any path satisfies the condition, return true

Approach: Recursive DFS

We use depth-first search with a decreasing target. At each node, we subtract its value from the remaining sum. When we reach a leaf, we check if the remaining sum equals the leaf's value.

Algorithm Steps

Base case 1: If node is null, return false (no path exists)
Base case 2: If node is a leaf (no children), check if its value equals the remaining sum
Recursively check left and right subtrees with targetSum - node.val
Return true if either subtree has a valid path

Idea Map

Start at root with targetSum

Is node null? → Return false

Is leaf (no left AND no right)?
return node.val == remainingSum

Recurse: hasPathSum(left, sum - val) OR hasPathSum(right, sum - val)

Return true/false

Complexity Analysis

Time Complexity

O(n) - In worst case, we visit every node once. If we find a valid path early, we may not visit all nodes.

Space Complexity

O(h) - Recursion stack depth equals tree height. Worst case O(n) for skewed tree, O(log n) for balanced.

Code


class TreeNode:
Definition for a binary tree node.
    def __init__(self, val=0, left=None, right=None):
Constructor initializes node with value and optional children.
        self.val = val
Store the node's value.
        self.left = left
Reference to left child.
        self.right = right
Reference to right child.


def hasPathSum(root: TreeNode, targetSum: int) -> bool:
Main function: check if any root-to-leaf path sums to target.
    if not root:
Base case: empty tree has no path.
        return False
Return False for null root.
    
Empty line for readability.
    # Check if this is a leaf node
Comment: leaf detection logic.
    if not root.left and not root.right:
Leaf condition: no left AND no right child.
        return root.val == targetSum
At leaf: check if value equals remaining sum.
    
Empty line.
    # Recursively check subtrees with reduced sum
Comment explaining recursion.
    remaining = targetSum - root.val
Calculate remaining sum after subtracting current node.
    return (hasPathSum(root.left, remaining) or
Recurse on left subtree with remaining sum.
            hasPathSum(root.right, remaining))
Recurse on right subtree. Return true if either path works.


public class TreeNode {
Definition for a binary tree node.
    int val;
Node's integer value.
    TreeNode left;
Reference to left child.
    TreeNode right;
Reference to right child.
}
End TreeNode class.


public boolean hasPathSum(TreeNode root, int targetSum) {
Main method: check if path exists with given sum.
    if (root == null) return false;
Base case: null node means no path.
    
Empty line.
    // Check if leaf node
Comment for leaf check.
    if (root.left == null && root.right == null) {
Leaf condition: both children are null.
        return root.val == targetSum;
At leaf: check if value equals target.
    }
End if block.
    
Empty line.
    int remaining = targetSum - root.val;
Calculate remaining sum after current node.
    return hasPathSum(root.left, remaining) ||
Recurse on left with remaining sum.
           hasPathSum(root.right, remaining);
Recurse on right. Return true if either works.
}
End method.


struct TreeNode {
Definition for a binary tree node struct.
    int val;
Node's integer value.
    TreeNode *left;
Pointer to left child.
    TreeNode *right;
Pointer to right child.
};
End TreeNode struct.


bool hasPathSum(TreeNode* root, int targetSum) {
Main function to check path sum.
    if (!root) return false;
Base case: null pointer returns false.
    
Empty line.
    // Check if leaf node
Comment for leaf check.
    if (!root->left && !root->right) {
Leaf condition using arrow operator.
        return root->val == targetSum;
At leaf: compare value to target.
    }
End if block.
    
Empty line.
    int remaining = targetSum - root->val;
Calculate remaining sum.
    return hasPathSum(root->left, remaining) ||
Recurse on left subtree.
           hasPathSum(root->right, remaining);
Recurse on right. Use || for OR logic.
}
End function.

Edge Cases & Common Mistakes

⚠️

Path must end at a leaf

A path that ends at an internal node doesn't count! Make sure to check that both left and right children are null before returning true.

💡

Negative values

The tree can contain negative values, so there might be multiple valid paths. The algorithm handles this automatically.

✓

Single node tree

If the tree has only the root node (which is also a leaf), check if root.val equals targetSum.

📝

Empty tree

If root is null, return false immediately since there's no path.

Understanding Tree Traversals

Path Sum relies on DFS traversal to explore all root-to-leaf paths. Master tree traversals to solve a wide variety of tree problems efficiently.

Learn more about tree traversals →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Path Sum' problem on LeetCode.

AlgoExplained.dev