0% completed
Problem Statement
Given a root
of the binary tree and an integer S
, return true
if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals S
. Otherwise, return false
.
Examples
Example 1:
- Input: root =
[1, 2, 3, 4, 5, 6, 7]
, S =10
- Expected Output:
true
- Justification: The tree has
1 -> 3 -> 6
root-to-leaf path having sum equal to 10.
Example 2:
- Input: root =
[12, 7, 1, 9, null, 10, 5]
, S =23
- Expected Output:
true
- Justification: The tree has
12 -> 1 -> 10
root-to-leaf path having sum equal to 23.
Example 3:
- Input: root =
[12, 7, 1, 9, null, 10, 5]
, S =16
- Expected Output:
false
- Justification: The tree doesn't have root-to-leaf path having sum equal to 16.
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]
. -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
Solution
The Binary Tree Path Sum
problem involves determining whether there is a root-to-leaf path in a binary tree such that the sum of the node values along the path equals a given target sum. The algorithm traverses the tree recursively, adjusting the target sum at each step by subtracting the value of the current node. At each step, we pass the updated target sum to the recursive DFS call. If a leaf node is reached and its value matches the adjusted sum, a valid path has been found.
Step-by-Step Algorithm
-
Check if the root is null:
- If the root is
null
, returnfalse
because there is no path in an empty tree.
- If the root is
-
Check if the current node is a leaf:
- If the current node is a leaf, and its value matches the current sum (target sum minus the values encountered so far), return
true
, indicating that a valid path has been found.
- If the current node is a leaf, and its value matches the current sum (target sum minus the values encountered so far), return
-
Traverse the left and right subtrees:
- If the current node is not a leaf, adjust the sum by subtracting the value of the current node from the target sum.
- Recursively check both the left and right children, passing the updated sum to both recursive calls.
-
Return true if any recursive call returns true:
- If any of the recursive calls (left or right subtree) returns
true
, returntrue
to indicate that a valid path has been found. - Otherwise, return
false
if neither of the recursive calls finds a valid path.
- If any of the recursive calls (left or right subtree) returns
Algorithm Walkthrough
-
Step 1 - Start at the root node (12):
- The current node is
12
. - The target sum is
23
. - Check if the current node is
null
: No. - Check if the current node is a leaf: No (it has left and right children).
- Subtract the current node's value from the target sum:
23 - 12 = 11
. - Now recursively check both the left and right subtrees, with the new sum
11
.
- The current node is
-
Step 2 - Traverse the left subtree (Node 7):
- The current node is
7
. - The target sum is
11
. - Check if the current node is
null
: No. - Check if the current node is a leaf: No (it has a left child).
- Subtract the current node's value from the target sum:
11 - 7 = 4
. - Now recursively check the left subtree with the new sum
4
(as the right child is null).
- The current node is
-
Step 3 - Traverse the left subtree (Node 9):
- The current node is
9
. - The target sum is
4
. - Check if the current node is
null
: No. - Check if the current node is a leaf: Yes (it has no left or right children).
- Check if the current node's value matches the target sum:
9 != 4
. - Since the values do not match, return
false
and backtrack to node7
.
- The current node is
-
Step 4 - Traverse the right subtree of Node 12 (Node 1):
- Backtrack to node
12
and now traverse its right subtree. - The current node is
1
. - The target sum is
11
(from step 1). - Check if the current node is
null
: No. - Check if the current node is a leaf: No (it has left and right children).
- Subtract the current node's value from the target sum:
11 - 1 = 10
. - Now recursively check both the left and right subtrees with the new sum
10
.
- Backtrack to node
-
Step 5 - Traverse the left subtree (Node 10):
- The current node is
10
. - The target sum is
10
. - Check if the current node is
null
: No. - Check if the current node is a leaf: Yes (it has no left or right children).
- Check if the current node's value matches the target sum:
10 == 10
. - Since the values match, return
true
indicating that a valid path (12 → 1 → 10) has been found.
- The current node is
-
Step 6 - Return final result:
- Since we found a valid path in step 5, the algorithm returns
true
for the input tree and sum23
.
- Since we found a valid path in step 5, the algorithm returns
Final Output:
- The tree has a path with a sum of
23
:12 → 1 → 10
. Hence, the result istrue
.
Code
Complexity Analysis
Time Complexity
The time complexity of the above algorithm is O(N), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.
Space Complexity
The space complexity of the above algorithm will be O(N) in the worst case. This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible