Path Sum
Easy · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree and an integer targetSum, return true if some root-to-leaf path has node values adding up to targetSum.
A path must start at the root and end at a leaf (a node with no children). If the tree is empty, return false.
The tests build trees with from_level([...]), a level-order list where None marks a missing child. Trees here run to 5,000 nodes and can be a single path that deep, so a solution that recurses once per level may run out of stack in Python.
Examples
Input: root = [10,5,-3,3,2,null,11], targetSum = 17 Output: true
The path 10 → 5 → 2 sums to 17.
Input: root = [10,5,-3,3,2,null,11], targetSum = 15 Output: false
The root-to-leaf sums are 18, 17 and 18; none equals 15. (10 → 5 sums to 15, but 5 is not a leaf.)
Input: root = [], targetSum = 0 Output: false
An empty tree has no root-to-leaf path.
Constraints
- 0 <= number of nodes <= 5000
- -1000 <= Node.val <= 1000
- -5 · 10^6 <= targetSum <= 5 · 10^6
Approaches
- Baseline: list every root-to-leaf path, then add — time O(n · h), space O(n · h)
Follow-up
What if the path could stop at any node, not only a leaf? The same walk works; compare the running sum at every node (see the use case “The path may stop at any node”).
Related problems
Start free on Cariara · Coding problems · System design studio
