112. Path Sum - Explanation

Description

You are 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 = [1,2,3], targetSum = 3

Output: true

Explanation: The root-to-leaf path with the target sum is 1 -> 2.

Example 2:

Input: root = [-15,10,20,null,null,15,5,-5], targetSum = 15

Output: true

Explanation: The root-to-leaf path with the target sum is -15 -> 20 -> 15 -> -5.

Example 3:

Input: root = [1,1,0,1], targetSum = 2

Output: false

Constraints:

0 <= The number of nodes in the tree <= 5000.
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Trees - Understanding tree structure, root, leaf nodes, and traversal concepts
Depth First Search (DFS) - Recursive tree traversal to explore paths from root to leaves
Recursion - Using recursive function calls to traverse tree structures

1. Depth First Search - I

Intuition

We traverse the tree from root to leaves, accumulating the sum along the way. When we reach a leaf node, we check if the accumulated sum equals the target. dfs naturally explores all root-to-leaf paths, making it ideal for this problem.

Algorithm

Define dfs(node, curSum) that returns whether a valid path exists from this node.
If node is null, return false.
Add node.val to curSum.
If node is a leaf (no children), return whether curSum == targetSum.
Otherwise, recursively check the left and right subtrees, returning true if either has a valid path.
Call dfs(root, 0) to start the search.

# 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:
        def dfs(node, curSum):
            if not node:
                return False

            curSum += node.val
            if not node.left and not node.right:
                return curSum == targetSum

            return dfs(node.left, curSum) or dfs(node.right, curSum)

        return dfs(root, 0)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return dfs(root, 0, targetSum);
    }

    private boolean dfs(TreeNode node, int curSum, int targetSum) {
        if (node == null) return false;

        curSum += node.val;
        if (node.left == null && node.right == null) {
            return curSum == targetSum;
        }

        return dfs(node.left, curSum, targetSum) || dfs(node.right, curSum, targetSum);
    }
}

/**
 * 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) {
        return dfs(root, 0, targetSum);
    }

private:
    bool dfs(TreeNode* node, int curSum, int targetSum) {
        if (node == nullptr) return false;

        curSum += node->val;
        if (node->left == nullptr && node->right == nullptr) {
            return curSum == targetSum;
        }

        return dfs(node->left, curSum, targetSum) || dfs(node->right, curSum, targetSum);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @param {number} targetSum
     * @return {boolean}
     */
    hasPathSum(root, targetSum) {
        const dfs = (node, curSum) => {
            if (!node) return false;

            curSum += node.val;
            if (!node.left && !node.right) {
                return curSum === targetSum;
            }

            return dfs(node.left, curSum) || dfs(node.right, curSum);
        };

        return dfs(root, 0);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        bool Dfs(TreeNode node, int curSum) {
            if (node == null) return false;

            curSum += node.val;
            if (node.left == null && node.right == null) {
                return curSum == targetSum;
            }

            return Dfs(node.left, curSum) || Dfs(node.right, curSum);
        }

        return Dfs(root, 0);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    var dfs func(node *TreeNode, curSum int) bool
    dfs = func(node *TreeNode, curSum int) bool {
        if node == nil {
            return false
        }

        curSum += node.Val
        if node.Left == nil && node.Right == nil {
            return curSum == targetSum
        }

        return dfs(node.Left, curSum) || dfs(node.Right, curSum)
    }

    return dfs(root, 0)
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        fun dfs(node: TreeNode?, curSum: Int): Boolean {
            if (node == null) return false

            val newSum = curSum + node.`val`
            if (node.left == null && node.right == null) {
                return newSum == targetSum
            }

            return dfs(node.left, newSum) || dfs(node.right, newSum)
        }

        return dfs(root, 0)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        func dfs(_ node: TreeNode?, _ curSum: Int) -> Bool {
            guard let node = node else { return false }

            let newSum = curSum + node.val
            if node.left == nil && node.right == nil {
                return newSum == targetSum
            }

            return dfs(node.left, newSum) || dfs(node.right, newSum)
        }

        return dfs(root, 0)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

2. Depth First Search - II

Intuition

Instead of accumulating a sum, we subtract each node's value from the target. When we reach a leaf, we check if the remaining target is zero. This approach avoids passing an extra parameter and keeps the logic clean.

Algorithm

If root is null, return false.
Subtract root.val from targetSum.
If root is a leaf, return whether targetSum == 0.
Recursively call the function on left and right children with the updated target.
Return true if either subtree finds a valid path.

# 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

        targetSum -= root.val
        return (self.hasPathSum(root.left, targetSum) or
                self.hasPathSum(root.right, targetSum) or
                (not targetSum and not root.left and not root.right))

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        targetSum -= root.val;
        return hasPathSum(root.left, targetSum) ||
               hasPathSum(root.right, targetSum) ||
               (targetSum == 0 && root.left == null && root.right == null);
    }
}

/**
 * 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;
        targetSum -= root->val;
        return hasPathSum(root->left, targetSum) ||
               hasPathSum(root->right, targetSum) ||
               (targetSum == 0 && !root->left && !root->right);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @param {number} targetSum
     * @return {boolean}
     */
    hasPathSum(root, targetSum) {
        if (!root) return false;
        targetSum -= root.val;
        return (
            this.hasPathSum(root.left, targetSum) ||
            this.hasPathSum(root.right, targetSum) ||
            (targetSum === 0 && !root.left && !root.right)
        );
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        targetSum -= root.val;
        return HasPathSum(root.left, targetSum) ||
               HasPathSum(root.right, targetSum) ||
               (targetSum == 0 && root.left == null && root.right == null);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    targetSum -= root.Val
    return hasPathSum(root.Left, targetSum) ||
           hasPathSum(root.Right, targetSum) ||
           (targetSum == 0 && root.Left == nil && root.Right == nil)
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        if (root == null) return false

        val remaining = targetSum - root.`val`
        return hasPathSum(root.left, remaining) ||
               hasPathSum(root.right, remaining) ||
               (remaining == 0 && root.left == null && root.right == null)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        guard let root = root else { return false }

        let remaining = targetSum - root.val
        return hasPathSum(root.left, remaining) ||
               hasPathSum(root.right, remaining) ||
               (remaining == 0 && root.left == nil && root.right == nil)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Iterative DFS

Intuition

We can simulate the recursive dfs using an explicit stack. Each stack entry stores a node and the remaining sum needed to reach the target from that node. This approach avoids recursion depth issues for very deep trees.

Algorithm

If root is null, return false.
Initialize a stack with (root, targetSum - root.val).
While the stack is not empty:
- Pop a node and its remaining sum.
- If it's a leaf and the remaining sum is zero, return true.
- Push the right child (if exists) with its updated remaining sum.
- Push the left child (if exists) with its updated remaining sum.
If the stack empties without finding a valid path, return false.

# 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

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();
        stack.push(root);
        sumStack.push(targetSum - root.val);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int currSum = sumStack.pop();

            if (node.left == null && node.right == null && currSum == 0) {
                return true;
            }

            if (node.right != null) {
                stack.push(node.right);
                sumStack.push(currSum - node.right.val);
            }

            if (node.left != null) {
                stack.push(node.left);
                sumStack.push(currSum - node.left.val);
            }
        }

        return false;
    }
}

/**
 * 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;

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

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

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

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

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

        return false;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @param {number} targetSum
     * @return {boolean}
     */
    hasPathSum(root, targetSum) {
        if (!root) return false;

        const stack = [[root, targetSum - root.val]];
        while (stack.length) {
            const [node, currSum] = stack.pop();

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

            if (node.right) {
                stack.push([node.right, currSum - node.right.val]);
            }

            if (node.left) {
                stack.push([node.left, currSum - node.left.val]);
            }
        }

        return false;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        Stack<(TreeNode, int)> stack = new Stack<(TreeNode, int)>();
        stack.Push((root, targetSum - root.val));

        while (stack.Count > 0) {
            var (node, currSum) = stack.Pop();

            if (node.left == null && node.right == null && currSum == 0) {
                return true;
            }

            if (node.right != null) {
                stack.Push((node.right, currSum - node.right.val));
            }
            if (node.left != null) {
                stack.Push((node.left, currSum - node.left.val));
            }
        }

        return false;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    type pair struct {
        node   *TreeNode
        curSum int
    }

    stack := []pair{{root, targetSum - root.Val}}
    for len(stack) > 0 {
        p := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if p.node.Left == nil && p.node.Right == nil && p.curSum == 0 {
            return true
        }

        if p.node.Right != nil {
            stack = append(stack, pair{p.node.Right, p.curSum - p.node.Right.Val})
        }
        if p.node.Left != nil {
            stack = append(stack, pair{p.node.Left, p.curSum - p.node.Left.Val})
        }
    }

    return false
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        if (root == null) return false

        val stack = ArrayDeque<Pair<TreeNode, Int>>()
        stack.addLast(Pair(root, targetSum - root.`val`))

        while (stack.isNotEmpty()) {
            val (node, currSum) = stack.removeLast()

            if (node.left == null && node.right == null && currSum == 0) {
                return true
            }

            node.right?.let {
                stack.addLast(Pair(it, currSum - it.`val`))
            }
            node.left?.let {
                stack.addLast(Pair(it, currSum - it.`val`))
            }
        }

        return false
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        guard let root = root else { return false }

        var stack: [(TreeNode, Int)] = [(root, targetSum - root.val)]
        while !stack.isEmpty {
            let (node, currSum) = stack.removeLast()

            if node.left == nil && node.right == nil && currSum == 0 {
                return true
            }

            if let right = node.right {
                stack.append((right, currSum - right.val))
            }
            if let left = node.left {
                stack.append((left, currSum - left.val))
            }
        }

        return false
    }
}

Time & Space Complexity

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

4. Breadth First Search

Intuition

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.

Algorithm

If root is null, return false.
Initialize a queue with (root, targetSum - root.val).
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.
Return false if no valid path is found.

# 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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>();
        nodeQueue.add(root);
        sumQueue.add(targetSum - root.val);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int currSum = sumQueue.poll();

            if (node.left == null && node.right == null && currSum == 0) {
                return true;
            }

            if (node.left != null) {
                nodeQueue.add(node.left);
                sumQueue.add(currSum - node.left.val);
            }

            if (node.right != null) {
                nodeQueue.add(node.right);
                sumQueue.add(currSum - node.right.val);
            }
        }

        return false;
    }
}

/**
 * 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;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @param {number} targetSum
     * @return {boolean}
     */
    hasPathSum(root, targetSum) {
        if (!root) return false;

        const queue = new Queue([[root, targetSum - root.val]]);
        while (!queue.isEmpty()) {
            const [node, currSum] = queue.pop();

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

            if (node.left) {
                queue.push([node.left, currSum - node.left.val]);
            }

            if (node.right) {
                queue.push([node.right, currSum - node.right.val]);
            }
        }

        return false;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        Queue<(TreeNode, int)> queue = new Queue<(TreeNode, int)>();
        queue.Enqueue((root, targetSum - root.val));

        while (queue.Count > 0) {
            var (node, currSum) = queue.Dequeue();

            if (node.left == null && node.right == null && currSum == 0) {
                return true;
            }

            if (node.left != null) {
                queue.Enqueue((node.left, currSum - node.left.val));
            }
            if (node.right != null) {
                queue.Enqueue((node.right, currSum - node.right.val));
            }
        }

        return false;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    type pair struct {
        node   *TreeNode
        curSum int
    }

    queue := []pair{{root, targetSum - root.Val}}
    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]

        if p.node.Left == nil && p.node.Right == nil && p.curSum == 0 {
            return true
        }

        if p.node.Left != nil {
            queue = append(queue, pair{p.node.Left, p.curSum - p.node.Left.Val})
        }
        if p.node.Right != nil {
            queue = append(queue, pair{p.node.Right, p.curSum - p.node.Right.Val})
        }
    }

    return false
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        if (root == null) return false

        val queue = ArrayDeque<Pair<TreeNode, Int>>()
        queue.addLast(Pair(root, targetSum - root.`val`))

        while (queue.isNotEmpty()) {
            val (node, currSum) = queue.removeFirst()

            if (node.left == null && node.right == null && currSum == 0) {
                return true
            }

            node.left?.let {
                queue.addLast(Pair(it, currSum - it.`val`))
            }
            node.right?.let {
                queue.addLast(Pair(it, currSum - it.`val`))
            }
        }

        return false
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        guard let root = root else { return false }

        var queue: [(TreeNode, Int)] = [(root, targetSum - root.val)]
        while !queue.isEmpty {
            let (node, currSum) = queue.removeFirst()

            if node.left == nil && node.right == nil && currSum == 0 {
                return true
            }

            if let left = node.left {
                queue.append((left, currSum - left.val))
            }
            if let right = node.right {
                queue.append((right, currSum - right.val))
            }
        }

        return false
    }
}

Time & Space Complexity

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

Common Pitfalls

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.