Path Sum In Binary Tree
Given a binary tree and a sum
. Write a method to check if there's a path from a root
to a leaf
where a sum
of nodes equals
to the given sum
.
Note: A
leaf
is a node without children
Example 1
Input: 1 sum = 15
/ \
2 3
/ /
4 5
/
6
Output: true
Explanation: path
1->3->5->6
Example 2
Input: 1 sum = 3
/ \
5 3
Output: false
Algorithm
The idea is to make a traversal while passing the sum
and reduce the sum by a node value.
- return
true
if sum equalszero
at a leaf node - return
false
if the sum not equalszero
at a leaf node
Let's check the idea step by step. Assume we have a tree and the sum (see below)
During the tree traversal, we reduce the sum on a node value. The result will look like this.
At a leaf node, we check the resulting sum:
- return
true
if sum equalszero
at a leaf node - return
false
if the sum not equalszero
at a leaf node
Try to answer the question. Will the algorithm work if a tree contains negative values?
Code
public bool HasPathSum(TreeNode root, int sum)
{
if (root == null)
{
return false;
}
sum -= root.Value;
if (root.Left == null && root.Right == null)
{
return sum == 0;
}
return HasPathSum(root.Left, sum) || HasPathSum(root.Right, sum);
}
Time Complexity: O(n)
Recent articles
Nice to read