Path Sum

Easy

#0112Time: O(N)Space: O(H)3 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Companies

PayPal TikTok Datadog

Prompt

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:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses recursion to traverse the tree in a depth-first manner. The core idea is to subtract the current node's value from the targetSum and pass this new sum to its children. The recursion continues until a leaf node is reached, at which point we check if the accumulated path sum equals the target.

Algorithm

1. Check if the root is null. If so, return false as there are no paths.
1. Check if the current root is a leaf node (root.left == null && root.right == null).
1. If it is a leaf, return true if root.val == targetSum, otherwise false.
1. If it's not a leaf, recursively call hasPathSum for the left child with targetSum - root.val.
1. Recursively call hasPathSum for the right child with targetSum - root.val.
1. Return true if either of the recursive calls returns true, indicating a path was found.

Walkthrough

The algorithm defines a function that takes a tree node and the remaining sum required to reach the target.

Base Case 1: If the current node is null, it means we've traversed past a leaf without finding a valid path from that branch, so we return false.
Path Sum Update: We update the required sum by subtracting the current node's value: newTargetSum = currentSum - node.val.
Base Case 2 (Leaf Node): If the current node is a leaf (it has no left or right child), we check if its value equals the remaining targetSum. If it does, it means the path from the root to this leaf adds up to the original targetSum, so we return true.
Recursive Step: If the current node is not a leaf, we recursively call the function for its left and right children with the updated targetSum. If either of these calls returns true (meaning a valid path was found in either the left or right subtree), we return true. Otherwise, we return false.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean hasPathSum(TreeNode root, int targetSum) {18        if (root == null) {19            return false;20        }21        22        // If it's a leaf node, check if its value equals the remaining targetSum23        if (root.left == null && root.right == null) {24            return targetSum == root.val;25        }26        27        // Recursively call for left and right children with updated targetSum28        boolean hasPathInLeft = hasPathSum(root.left, targetSum - root.val);29        boolean hasPathInRight = hasPathSum(root.right, targetSum - root.val);30        31        return hasPathInLeft || hasPathInRight;32    }33}

Complexity

Time

O(N)

Space

O(H)

Trade-offs

Pros

Very intuitive and easy to read.
The code is concise and directly reflects the problem's recursive structure.

Cons

For very deep trees, this can lead to a StackOverflowError due to the depth of the recursion stack.

An alternative to recursion is to use an iterative approach with an explicit data structure, like a Stack for Depth-First Search (DFS) or a Queue for Breadth-First Search (BFS). This approach avoids the limitations of the recursion stack depth and can be more efficient in terms of space for certain tree structures.

Algorithm

1. If root is null, return false.
1. Create a nodeStack and a sumStack.
1. Push root to nodeStack and targetSum - root.val to sumStack.
1. Loop as long as nodeStack is not empty:
- a. Pop currentNode from nodeStack and currentSum from sumStack.
- b. If currentNode is a leaf and currentSum is 0, return true.
- c. If currentNode.right exists, push it to nodeStack and push currentSum - currentNode.right.val to sumStack.
- d. If currentNode.left exists, push it to nodeStack and push currentSum - currentNode.left.val to sumStack.
1. If the loop finishes, return false.

Walkthrough

We can simulate the recursive DFS approach using an explicit Stack. The idea is to maintain a stack of nodes to visit and another stack to store the remaining sum corresponding to each node.

Initialization: If the root is null, return false. Otherwise, push the root node onto a nodeStack and the initial remaining sum (targetSum - root.val) onto a sumStack.
Traversal Loop: While the stacks are not empty, pop a node and its corresponding sum.
Leaf Check: If the popped node is a leaf node and its corresponding remaining sum is zero, we have found a valid path. Return true.
Push Children: If the node is not a leaf, push its children (if they exist) onto the nodeStack. For each child, push the updated remaining sum (currentSum - child.val) onto the sumStack.
No Path Found: If the loop completes without returning, it means no such path exists. Return false.

A similar logic can be applied using a Queue for a BFS traversal, where nodes and sums are enqueued and dequeued instead of pushed and popped.

1// Iterative DFS using a Stack2import java.util.Stack;3 4class Solution {5    public boolean hasPathSum(TreeNode root, int targetSum) {6        if (root == null) {7            return false;8        }9 10        Stack<TreeNode> nodeStack = new Stack<>();11        Stack<Integer> sumStack = new Stack<>();12        13        nodeStack.push(root);14        sumStack.push(targetSum - root.val);15 16        while (!nodeStack.isEmpty()) {17            TreeNode currentNode = nodeStack.pop();18            int currentSum = sumStack.pop();19 20            if (currentNode.left == null && currentNode.right == null && currentSum == 0) {21                return true;22            }23 24            if (currentNode.right != null) {25                nodeStack.push(currentNode.right);26                sumStack.push(currentSum - currentNode.right.val);27            }28            if (currentNode.left != null) {29                nodeStack.push(currentNode.left);30                sumStack.push(currentSum - currentNode.left.val);31            }32        }33        return false;34    }35}

Complexity

Time

O(N)

Space

O(H) for DFS, O(W) for BFS

Trade-offs

Pros

Avoids StackOverflowError for very deep trees, making it more robust than the recursive solution.
The space complexity can be better than the alternative depending on the tree's shape (DFS is better for wide trees, BFS for deep/skewed trees).

Cons

The code is generally more verbose and less intuitive than the recursive counterpart.
Requires managing an explicit data structure (stack or queue).

Solutions

Solution

1/** * 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; * } * } */ class Solution { public boolean hasPathSum ( TreeNode root , int targetSum ) { return dfs ( root , targetSum ); } private boolean dfs ( TreeNode root , int s ) { if ( root == null ) { return false ; } s -= root . val ; if ( root . left == null && root . right == null && s == 0 ) { return true ; } return dfs ( root . left , s ) || dfs ( root . right , s ); } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {boolean} */ var hasPathSum =2  function (root, targetSum) {3    function dfs(root, s) {4      if (!root) return false;5      s += root.val;6      if (!root.left && !root.right && s == targetSum) return true;7      return dfs(root.left, s) || dfs(root.right, s);8    }9    return dfs(root, 0);10  };

1/** * 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 ) { function < bool ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int s ) -> int { if ( ! root ) return false ; s += root -> val ; if ( ! root -> left && ! root -> right && s == targetSum ) return true ; return dfs ( root -> left , s ) || dfs ( root -> right , s ); }; return dfs ( root , 0 ); } };

1# 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 ( root , s ): if root is None : return False s += root . val if root . left is None and root . right is None and s == targetSum : return True return dfs ( root . left , s ) or dfs ( root . right , s ) return dfs ( root , 0 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem