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 <= 1000The Path Sum problem asks whether a binary tree contains a root-to-leaf path whose node values add up to a given target sum. The key observation is that each step down the tree contributes to the cumulative sum, so the problem naturally fits a Depth-First Search (DFS) traversal.
In a DFS approach, you recursively move from the root to its children while subtracting the current node value from the remaining target. When you reach a leaf node, check if the remaining sum equals that node’s value. If it does, a valid path exists. This method efficiently explores all root-to-leaf paths while keeping track of the remaining sum.
An alternative approach uses Breadth-First Search (BFS) with a queue that stores nodes along with their cumulative sums. Both strategies traverse each node at most once, making them efficient for this task. DFS is often preferred due to its simplicity and natural fit for recursive tree traversal.
The traversal touches each node once, leading to O(n) time complexity, where n is the number of nodes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (Recursive) | O(n) | O(h) |
| Breadth-First Search (Queue) | O(n) | O(n) |
Greg Hogg
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.
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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
6 this.val = val;
7 this.left = left;
8 this.right = right;
9 }
10}
11
12public class Solution {
13 public bool HasPathSum(TreeNode root, int targetSum) {
14 if (root == null) return false;
if (root.left == null && root.right == null) return root.val == targetSum;
targetSum -= root.val;
return HasPathSum(root.left, targetSum) || HasPathSum(root.right, targetSum);
}
}This C# solution mirrors the approach of evaluating at each TreeNode if the current path sum could potentially satisfy the target sum, focusing particularly on when a leaf node is encountered.
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.
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).
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
std::stack<TreeNode*> nodes;
std::stack<int> sums;
nodes.push(root);
sums.push(root->val);
while (!nodes.empty()) {
TreeNode* currentNode = nodes.top(); nodes.pop();
int currentSum = sums.top(); sums.pop();
if (!currentNode->left && !currentNode->right && currentSum == targetSum) {
return true;
}
if (currentNode->right) {
nodes.push(currentNode->right);
sums.push(currentSum + currentNode->right->val);
}
if (currentNode->left) {
nodes.push(currentNode->left);
sums.push(currentSum + currentNode->left->val);
}
}
return false;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Path Sum and its variations frequently appear in technical interviews at major tech companies. It tests understanding of tree traversal, recursion, and managing cumulative state during traversal.
The most common approach is Depth-First Search (DFS). By recursively traversing the tree and subtracting each node’s value from the target sum, you can determine if any root-to-leaf path satisfies the condition. This method is efficient and easy to implement.
Binary trees are naturally traversed using recursion or a stack/queue. DFS typically uses recursion or an explicit stack, while BFS uses a queue to track nodes and cumulative sums during traversal.
The problem definition specifically requires the path to start at the root and end at a leaf node. This constraint ensures that partial paths ending at intermediate nodes are not considered valid solutions.
The C++ implementation similarly uses stacks for managing traversal, keeping track of each path sum actively without recursion. Stacks provide storage for nodes and path sums to enable iterative depth-first exploration, culminating checks at leaf nodes.