Leetcode 112. Path Sum

Problem

Given a binary tree and a sum, you need to determine whether there's a root-to-leaf path such that adding up all the values along the path equals the given sum. A leaf is a node without any children.

As an example, let's consider the following binary tree and sum = 22:

1
2
3      5
4     / \
5    4   8
6   /   / \
7  11  13  4
8 /  \      \
97    2      1

True should be returned because there exists a root-to-leaf path (5->4->11->2) which sums up to 22.

Approach

Our aim is to see if there is any path from the root running to the leaves in a way that the sum of its values equals given sum. Thus, we start from the root node, subtract its value from the given sum and then apply the same to the left and right child nodes, recursively. This would check all the conditions in those nodes too. When we find a node that is a leaf node and the sum equals its value, we know we have found a desired path.

Let's look at how the algorithm works on the example:

1
2
3      5   |
4     / \  |
5    4   8 |
6   /   /  |
7  11  13  4  |
8 /  \     /  |
97    2   1   |

We start from 5. 22 - 5 = 17. We then go to the left child node, namely 4, from which we subtract 17: 17 - 4 = 13. This process repeats until we reach the leaf node 2. At this point the sum is 2 as well. Thus, we return true.

Solutions

Python

1
2python
3class Solution:
4    def hasPathSum(self, root, sum):
5        if root is None:
6            return False
7        if root.val == sum and root.left is None and root.right is None:
8            return True
9        return self.hasPathSum(root.left, sum - root.val) or \
10               self.hasPathSum(root.right, sum - root.val)

Java

1
2java
3public class Solution {
4    public boolean hasPathSum(TreeNode root, int sum) {
5        if (root == null)
6            return false;
7        if (root.val == sum && root.left == null && root.right == null)
8            return true;
9        return hasPathSum(root.left, sum - root.val) ||
10               hasPathSum(root.right, sum - root.val);
11    }
12}

JavaScript

1
2javascript
3var hasPathSum = function(root, sum) {
4    if (!root) 
5        return false;
6    if (!root.left && !root.right)  
7        return sum === root.val;
8    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
9};

C++

1
2cpp
3class Solution {
4public:
5    bool hasPathSum(TreeNode* root, int sum) {
6        if (!root) 
7            return false;
8        if (!root->left && !root->right)
9            return sum==root->val;
10        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
11    }
12};

C#

1
2csharp
3public class Solution {
4    public bool HasPathSum(TreeNode root, int sum) {
5        if (root == null) 
6            return false;
7        if (root.val == sum && root.left == null && root.right == null) 
8            return true;
9        return HasPathSum(root.left, sum - root.val) || HasPathSum(root.right, sum - root.val);
10    }
11}

These solutions rely on the concept of depth-first search (DFS) in Tree. DFS starts traversal from the root node and traverses as far as possible along each branch before backtracking. This property is well suited for situations such as this where we are looking for a target value root-to-leaf path sum.

The time complexity for these solutions is O(n), where n is the number of nodes of the tree. In the worst-case scenario, we have to visit each node once when the sum does not exist in the tree or the leaf that ends the sum is the last node visited.

The space complexity also is O(n) in the worst-case scenario. The extra space comes from implicit stack space due to recursion. The maximum amount of space is taken up by the recursive stack in the case of a skewed binary tree. But in the case of a balanced tree, it would be O(log n).

This problem can be treated as a specific version of Tree Path Sum, therefore it's a good practice to try other related problems like counting the total number of such paths, returning all such paths, find the maximum path sum, path with a given sequence and so on. Practice makes perfect, especially in programming and problem-solving.

Thus, methods like DFS and understanding other concepts used in understanding data structures like binary trees can give you an advantage in being able to solve these types of problems in different programming languages like Python, Java, JavaScript, C++, and C#.