Watch 10 video solutions for Path Sum, a easy level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 94,035 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |