112. Path Sum
Problem Description
The problem presents a binary tree where each node contains an integer value. The goal is to find out if there is a path from the root node down to any leaf node such that the sum of the values of all the nodes along the path is equal to the given integer targetSum
. A leaf node is defined as a node that does not have any children. If such a path exists, the function should return true
; otherwise, it should return false
.
Flowchart Walkthrough
To determine the optimal algorithm for solving Leetcode 112. Path Sum, we will utilize the algorithm flowchart. Here's a detailed breakdown using the flowchart:
Is it a graph?
- Yes: The problem is based on a tree, which is a specific type of graph.
Is it a tree?
- Yes: The problem explicitly involves traversing a binary tree to find if there exists a path that sums to a given value.
Consequently, following the decision from the flowchart, we would opt to use Depth First Search (DFS) for this problem. DFS is particularly suitable for problems involving trees where we need to explore all possible paths or a condition-specific path, as is required in the Path Sum problem to check different root-to-leaf paths.
Conclusion: According to the flowchart, we should apply DFS for solving this tree-based problem efficiently.
Intuition
The solution to this problem is based on the Depth-First Search (DFS) algorithm. DFS is a common tree traversal method that can be used efficiently to search all possible paths in a tree from the root node down to the leaves.
The intuition behind using DFS in this particular problem is the need to explore each possible path fully before moving to an alternative path. We traverse down one branch of the tree, adding the values of each node we pass through, until we reach a leaf. Once at a leaf, we check if the accumulated sum is equal to targetSum
.
If we hit a leaf and the sum does not equal targetSum
, we backtrack and try a different path. This backtracking is naturally handled by the call stack in a recursive DFS approach.
Thus, the solution approach is to start from the root and explore each branch recursively, carrying forwards the cumulative sum. If at any point we reach a leaf and the sum matches targetSum
, we return true
. Otherwise, if we exhaust all paths and none meet the criteria, we return false
.
As part of the recursion, we ensure two things:
- If the current node is
None
(i.e., we've reached beyond a leaf), this path is not valid, and we returnfalse
. - When we reach a leaf node (both its children are
None
), we check if the cumulative sum equalstargetSum
and return the result of this comparison.
The provided code defines a nested dfs
function inside the main function hasPathSum
that handles the recursive traversal and the accumulation of the sum.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
Solution Approach
The solution utilizes a straightforward recursive DFS strategy. By defining a helper function dfs(root, s)
, we can keep track of the current sum s
as we traverse down the tree. The base case checks if the current node root
is None
, meaning that the path has reached beyond a leaf node, and hence, it returns False
since there cannot be a valid path through a non-existing node.
When the recursive function dfs
is called, it performs the following steps:
- It first checks if the current node is
None
. If true, the recursion stops and returnsFalse
. - If the current node is not
None
, it adds the node's value to the ongoing sums
. - Next, it checks if the current node is a leaf (both
root.left
androot.right
areNone
). If it is a leaf, ands
equalstargetSum
, it indicates that a valid path has been found and returnsTrue
. - If the current node is not a leaf, the function proceeds to call itself recursively for both the left and right children of the current node, if they exist (
dfs(root.left, s)
anddfs(root.right, s)
). - The result of these recursive calls is combined using logical OR (
or
), which means if either the left or the right subtree has a valid path, the function will returnTrue
.
The dfs
function encapsulates the logic for searching the tree and determining if a valid path exists that sums up to targetSum
. It is initiated by passing the root of the tree and an initial sum of 0
to the dfs
function.
Here is how the dfs
function is implemented within the context of the provided solution code snippet:
1def dfs(root, s):
2 if root is None: # Base case: empty node, return False
3 return False
4 s += root.val # Increment the sum by the current node's value
5 # If it's a leaf and the sum matches targetSum, return True
6 if root.left is None and root.right is None and s == targetSum:
7 return True
8 # Recursively search the left and right subtrees
9 return dfs(root.left, s) or dfs(root.right, s)
And the hasPathSum
function then calls this dfs
function with the initial parameters:
1return dfs(root, 0)
In summary, the recursive function explores all possible paths from the root to each leaf, checking for a match against targetSum
. It returns True
as soon as a valid path is found, or False
if no such path exists, effectively implementing a depth-first search for the problem at hand.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Assume we have the following binary tree and targetSum
of 22.
1 5 2 / \ 3 4 8 4 / / \ 5 11 13 4 6 / \ \ 7 7 2 1
Now, let's follow the dfs
function to see how it works:
-
Begin at the root (node with value 5), with a starting sum
s
of 0. Calldfs(root=5, s=0)
. -
At root (5),
s
becomes 5 (0 + 5
). This node is not a leaf, so we make recursive calls for left and right children.- Call
dfs(root=4, s=5)
to continue on the left child.
- Call
-
At node 4,
s
becomes 9 (5 + 4
). This is also not a leaf. Recursive call on left child.- Call
dfs(root=11, s=9)
.
- Call
-
At node 11,
s
becomes 20 (9 + 11
). Not a leaf, we have two children, so we make two recursive calls.- First, call
dfs(root=7, s=20)
. - Then we will call
dfs(root=2, s=20)
, but let's follow the first call for now.
- First, call
-
At node 7,
s
becomes 27 (20 + 7
). This is a leaf, buts
is not equal to thetargetSum
of 22. ReturnsFalse
.- Backtrack to node 11 and proceed with the second call,
dfs(root=2, s=20)
.
- Backtrack to node 11 and proceed with the second call,
-
At node 2,
s
becomes 22 (20 + 2
). This is a leaf ands
matchestargetSum
. ReturnsTrue
.
Once True
is encountered, the function does not need to explore any further branches. The propagation of True
through the recursive calls will eventually lead to the hasPathSum
function returning True
, indicating that there is a path that adds up to the targetSum
of 22.
The binary tree has successfully been searched with a depth-first approach to find a path sum that matches the target. In this case, the path with values [5, 4, 11, 2]
yields the desired sum, and so our problem is solved with the function returning True
.
Solution Implementation
1# Definition for a binary tree node.
2class TreeNode:
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val
5 self.current_sum = left
6 self.right = right
7
8class Solution:
9 def hasPathSum(self, root: Optional[TreeNode], target_sum: int) -> bool:
10 """
11 Determines if the tree has a root-to-leaf path such that
12 adding up all the values along the path equals the given sum.
13
14 :param root: TreeNode, the root of the binary tree
15 :param target_sum: int, the target sum to be achieved
16 :return: bool, True if such a path exists, False otherwise
17 """
18
19 def dfs(node, current_sum):
20 """
21 Depth-first search helper function that traverses the tree
22 to find a root-to-leaf path that sums to the target_sum.
23
24 :param node: TreeNode, the current node being traversed
25 :param current_sum: int, the sum of the values from the root node up to the current node
26 :return: bool, True if a path is found, False otherwise
27 """
28 if node is None:
29 # Base case: if the current node is None, no path exists
30 return False
31
32 # Update the current_sum by adding the current node's value
33 current_sum += node.val
34
35 # Check if the current node is a leaf and matches the target_sum
36 if node.left is None and node.right is None and current_sum == target_sum:
37 return True
38
39 # Recursively search in the left and right subtrees for the path
40 # If either subtree returns True, a valid path has been found
41 return dfs(node.left, current_sum) or dfs(node.right, current_sum)
42
43 # Start DFS traversal from the root with an initial sum of 0
44 return dfs(root, 0)
45
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8
9 TreeNode() {}
10
11 TreeNode(int val) {
12 this.val = val;
13 }
14
15 TreeNode(int val, TreeNode left, TreeNode right) {
16 this.val = val;
17 this.left = left;
18 this.right = right;
19 }
20}
21
22class Solution {
23 /**
24 * Returns true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given target sum.
25 *
26 * @param root The root of the binary tree.
27 * @param targetSum The target sum to find.
28 * @return True if such a path exists, otherwise false.
29 */
30 public boolean hasPathSum(TreeNode root, int targetSum) {
31 return hasPathSumDFS(root, targetSum);
32 }
33
34 /**
35 * Helper method to perform depth-first search to find the path sum.
36 *
37 * @param node The current node being visited.
38 * @param currentSum The sum accumulated so far.
39 * @return True if a path with the given sum is found, otherwise false.
40 */
41 private boolean hasPathSumDFS(TreeNode node, int currentSum) {
42 // If the node is null, we've hit a dead end and should return false.
43 if (node == null) {
44 return false;
45 }
46
47 // Subtract the value of current node from current sum.
48 currentSum -= node.val;
49
50 // Check if the current node is a leaf and the current sum equals zero,
51 // which means we've found a path with the required sum.
52 if (node.left == null && node.right == null && currentSum == 0) {
53 return true;
54 }
55
56 // Recursively check the left and right subtrees for the remaining sum.
57 // If either subtree returns true, a path has been found.
58 return hasPathSumDFS(node.left, currentSum) || hasPathSumDFS(node.right, currentSum);
59 }
60}
61
1// Definition for a binary tree node
2struct TreeNode {
3 int val;
4 TreeNode *left;
5 TreeNode *right;
6 // Constructor to initialize a tree node with a value and optional left and right children
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8 // Constructor to initialize a tree node with a value and both children
9 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14 // Checks if the binary tree has a root-to-leaf path that sums up to the targetSum
15 bool hasPathSum(TreeNode* root, int targetSum) {
16 // Lambda function that performs depth-first search on the tree to find path sum
17 // [&] captures local variables by reference
18 std::function<bool(TreeNode*, int)> dfs = [&](TreeNode* node, int sumSoFar) -> bool {
19 // If the node is null, return false as we've reached beyond a leaf node
20 if (!node) return false;
21
22 // Add the current node's value to the running sum
23 sumSoFar += node->val;
24
25 // Check if the current node is a leaf and the sum equals the targetSum
26 if (!node->left && !node->right && sumSoFar == targetSum) {
27 return true;
28 }
29
30 // Continue searching in the left and right subtrees
31 // If any of the recursive calls return true, the whole expression will be true
32 // Utilize the short-circuit evaluation of the '||' operator
33 return dfs(node->left, sumSoFar) || dfs(node->right, sumSoFar);
34 };
35
36 // Start the depth-first search from the root node with an initial sum of 0
37 return dfs(root, 0);
38 }
39};
40
1// Typescript type definition for a binary tree node.
2type TreeNode = {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6};
7
8/**
9 * Determines if the binary tree has a root-to-leaf path that sums up to the given target sum.
10 *
11 * @param {TreeNode | null} root - The root node of the binary tree.
12 * @param {number} targetSum - The target sum to find the path for.
13 * @returns {boolean} - True if such a path exists, otherwise False.
14 */
15function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
16 // If the root is null, there is no path, return false.
17 if (root === null) {
18 return false;
19 }
20
21 // Destructure the current node to get its value and its children.
22 const { val, left, right } = root;
23
24 // If the node is a leaf (no left or right children),
25 // Check if subtracting the node's value from the target sum equals 0.
26 if (left === null && right === null) {
27 return targetSum - val === 0;
28 }
29
30 // Recursively check the left and right subtrees reducing the target sum by the current node's value.
31 // Return true if either subtree has a path that sums up to the adjusted target sum.
32 return hasPathSum(left, targetSum - val) || hasPathSum(right, targetSum - val);
33}
34
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
, where n
is the number of nodes in the binary tree. The reason for this is that the code implements a depth-first search (DFS) algorithm, which visits each node exactly once in the worst-case scenario.
Space Complexity
The space complexity of the code is O(h)
, where h
is the height of the binary tree. This space is used by the execution stack for recursive calls. In the worst-case scenario where the tree is completely unbalanced, the space complexity will be O(n)
. But on a balanced tree, the height h
can be considered as O(log n)
, making the average space complexity O(log n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.