Path Sum
The key idea
Carry the remaining target down the tree: subtract each node's value as you descend. A path works exactly when you reach a leaf and the remaining target is exactly that leaf's value (so it hits zero there). Only leaves count as path ends, never internal nodes.
Problem
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. Return false otherwise.
A leaf is a node with no children. A root-to-leaf path starts at the root and ends at any leaf, following parent-to-child links the whole way down.
Constraints
- The number of nodes in the tree is in the range
[0, 5000]. -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Examples
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Input: root = [1,2,3], targetSum = 5
Output: false
Input: root = [], targetSum = 0
Output: false
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM