Path Sum

Easy
1867.

Path Sum

Path Sum is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

Given the root of a binary tree and an integer targetSum, return true if some path from the root down to a leaf has node values adding up to exactly targetSum, and false otherwise. A leaf is a node with no children; an empty tree has no paths.

Example 1

Input
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output
true
Explanation
The path 5 → 4 → 11 → 2 sums to 22.

Example 2

Input
root = [1,2,3], targetSum = 5
Output
false
Explanation
The two root-to-leaf paths sum to 3 and 4.

Example 3

Input
root = [], targetSum = 0
Output
false
Explanation
An empty tree has no root-to-leaf path at all, not even one with sum 0.

Constraints

  • The number of nodes in the tree is in the range [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Path Sum — Solution in Python, Java & C++

Path Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Microsoft.

Path Sum is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

Problem statement

Given the root of a binary tree and an integer targetSum, return true if some path from the root down to a leaf has node values adding up to exactly targetSum, and false otherwise. A leaf is a node with no children; an empty tree has no paths.

Example 1

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The path 5 → 4 → 11 → 2 sums to 22.

Example 2

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: The two root-to-leaf paths sum to 3 and 4.

Example 3

Input: root = [], targetSum = 0
Output: false
Explanation: An empty tree has no root-to-leaf path at all, not even one with sum 0.

Constraints

  • The number of nodes in the tree is in the range [0, 5000]
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Hints for Path Sum

  1. Hint 1

    Walking down from the root, keep track of how much of the target is still left.

  2. Hint 2

    Subtract each node's value as you descend; at a leaf, check whether exactly zero remains.

  3. Hint 3

    The path must end at a leaf — a node with one child is not an end point. Values may be negative, so you cannot stop early when the running sum passes the target.

How to solve Path Sum

Carry the remaining target down the tree. At a leaf the path is complete, and it qualifies exactly when the remainder equals the leaf's value.

Approach

  1. If root is null, return false.
  2. Let rest = targetSum - root.val.
  3. If root is a leaf, return rest == 0.
  4. Otherwise return hasPathSum(root.left, rest) || hasPathSum(root.right, rest).

Why it works

Every root-to-leaf path is followed by exactly one chain of recursive calls, and along that chain rest equals the target minus the values seen so far. The null base case returns false, so a node with one child cannot end a path through its missing side.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth

Pitfalls

  • Returning targetSum == 0 at a null child lets a one-child node count as a leaf.
  • Negative values mean partial sums can overshoot and come back — no pruning on sign.
  • An empty tree with targetSum = 0 is false.

Reference solution

Python

from typing import Optional

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    if root is None:
        return False
    rest = targetSum - root.val
    if root.left is None and root.right is None:
        return rest == 0
    return hasPathSum(root.left, rest) or hasPathSum(root.right, rest)

Java

public static boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    int rest = targetSum - root.val;
    if (root.left == null && root.right == null) return rest == 0;
    return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
}

C++

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    int rest = targetSum - root->val;
    if (!root->left && !root->right) return rest == 0;
    return hasPathSum(root->left, rest) || hasPathSum(root->right, rest);
}

JavaScript

var hasPathSum = function(root, targetSum) {
    if (root === null) return false;
    var rest = targetSum - root.val;
    if (root.left === null && root.right === null) return rest === 0;
    return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)