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.
A leaf is a node with no children.
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 with the target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There are two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5.
Example 3:
Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths.
Constraints:
[0, 5000].-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000Problem Overview: Given the root of a binary tree and an integer targetSum, determine whether the tree has a root‑to‑leaf path where the sum of node values equals the target. A valid path must start at the root and end at a leaf node.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
The recursive DFS approach walks down the tree while subtracting the current node’s value from targetSum. Each recursive call moves to either the left or right child with the updated remaining sum. When you reach a leaf node (both children are null), check whether the remaining sum equals the node’s value. If it does, a valid root-to-leaf path exists. This method naturally fits recursive traversal of a tree and keeps the implementation clean because the call stack tracks the current path automatically. Time complexity is O(n) since every node may be visited once. Space complexity is O(h), where h is the height of the tree, due to recursion stack usage.
Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))
An iterative version replaces recursion with an explicit stack. Each stack entry stores a node and the remaining sum required for that path. Start by pushing the root and the original target sum. During traversal, pop the top node, subtract its value from the remaining sum, and check if it is a leaf node with the correct total. If not, push its children onto the stack with the updated remaining sum. This approach mirrors recursive depth-first search but gives you direct control over traversal and avoids recursion limits. Time complexity remains O(n) because each node is processed once. Space complexity is O(h) in the average case, corresponding to the maximum stack depth in a binary tree.
Recommended for interviews: The recursive DFS solution is what most interviewers expect first. It clearly shows that you understand root-to-leaf traversal and how to propagate state (the remaining sum) through recursion. After presenting the recursive version, mentioning the iterative stack-based DFS demonstrates deeper knowledge of traversal mechanics and how recursion can be simulated with an explicit stack.
This approach uses a recursive DFS strategy to navigate from the root to each leaf, calculating the cumulative sum along the path. If we find a path where the cumulative sum equals the targetSum at a leaf node, we return true. Otherwise, we continue exploring other paths. In case we exhaust all paths without finding a valid path, we return false.
In this Python solution, we define a recursive function hasPathSum that deducts the current node's value from targetSum as we traverse the tree. If we reach a leaf node (both children are None) and the remaining targetSum equals the leaf node's value, we return true; otherwise, false. The recursion continues for left and right subtrees.
Time Complexity: O(N), where N is the number of nodes in the tree, as we have to visit each node.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack.
In contrast to the recursive method, this approach utilizes an explicit stack to iteratively perform DFS, tracking the cumulative sum along each path. Nodes are pushed onto the stack with their cumulative sums traversed thus far, effectively replacing the recursion stack with an explicit stack to manage state manually. This can help in environments with limited recursion support.
The Python solution leverages a stack to simulate DFS. When visiting a node, the accumulated sum of the path is tracked, ensuring each leaf node is evaluated against targetSum. Left and right children are pushed onto the stack with updated path sums.
Time Complexity: O(N), examining each node iteratively.
Space Complexity: O(N), as the stack could store up to all nodes in the worst scenario (e.g., a path-heavy tree with a single path).
Starting from the root node, recursively traverse the tree and update the value of the node to the path sum from the root node to that node. When you traverse to a leaf node, determine whether this path sum is equal to the target value. If it is equal, return true, otherwise return false.
The time complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited once.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(N), where N is the number of nodes in the tree, as we have to visit each node. |
| Iterative Depth-First Search with Stack | Time Complexity: O(N), examining each node iteratively. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Cleanest implementation for tree traversal; ideal for interviews and typical binary tree recursion problems. |
| Iterative DFS with Stack | O(n) | O(h) | Useful when avoiding recursion limits or when you want explicit control over traversal order. |
Path Sum - Leetcode 112 - Python • NeetCode • 94,035 views views
Watch 9 more video solutions →Practice Path Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor