Path Sum

Easy · Trees · Explanation and code example

Breadth First Search

How it works

bfs explores the tree level by level. We use a queue to store each node along with the remaining sum needed. When we reach a leaf, we check if the target has been met. BFS guarantees we explore all paths systematically.

Steps

  1. If root is null, return false.
  2. Initialize a queue with (root, targetSum - root.val).
  3. While the queue is not empty:
    • Dequeue a node and its remaining sum.
    • If it's a leaf and the remaining sum is zero, return true.
    • Enqueue the left child (if exists) with its updated remaining sum.
    • Enqueue the right child (if exists) with its updated remaining sum.
  4. Return false if no valid path is found.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Checking Sum at Non-Leaf Nodes

A frequent mistake is checking if the current sum equals the target at every node rather than only at leaf nodes. The problem specifically requires a root-to-leaf path, so internal nodes should not trigger a true result even if the running sum matches the target. Always verify that both left and right children are null before comparing sums.

Returning True on Null Nodes When Target is Zero

Another pitfall is incorrectly returning true when reaching a null node if targetSum happens to be zero. An empty tree (null root) should return false regardless of the target value. The base case for null nodes should always return false, and the sum check should only occur at actual leaf nodes.

Python code example

from typing import Optional
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        queue = deque([(root, targetSum - root.val)])
        while queue:
            node, curr_sum = queue.popleft()
            if not node.left and not node.right and curr_sum == 0:
                return True
            if node.left:
                queue.append((node.left, curr_sum - node.left.val))
            if node.right:
                queue.append((node.right, curr_sum - node.right.val))
        return False

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;

        queue<pair<TreeNode*, int>> q;
        q.push({root, targetSum - root->val});

        while (!q.empty()) {
            auto [node, currSum] = q.front();
            q.pop();

            if (!node->left && !node->right && currSum == 0) {
                return true;
            }

            if (node->left) {
                q.push({node->left, currSum - node->left->val});
            }

            if (node->right) {
                q.push({node->right, currSum - node->right->val});
            }
        }

        return false;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations