112. Path Sum

Path Sum

Problem Description 

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 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



Approach) Recursive

In this challenge, the logic is pretty simple:

• Traverse through a tree branch

• Add up all values of the branch

• Once we reach a leaf, i.e. node without any children nodes, check if our sum from #2 here is equal targetSum

• If it’s false keep checking

The recursive function will be used to solve this problem since we don’t really want to check each Node once we have a match.

Idea: 

I’ll call my recursive function checkTree and it will take the following arguments root, targetSum, sum.

function checkTree(root, targetSum, sum) {....}

It makes sense to check if root exists in the first place, so we can throw a simple if statement first.

if (!root) {  return false;}

Now we can start populating sum for the current branch.

sum += root.val;

Now, we’re at the point where we want to know if we’ve reached the leaf (i.e. the end of the branch) by checking if root has any children. If the root is the leaf, then we should check if sum is equal to targetSum and return true or false.

if (root.left === null && root.right === null) {  return sum === targetSum;}

Otherwise, let's dive in further using checkTree function on children nodes.

return checkTree(root.left, targetSum, sum) || checkTree(root.right, targetSum, sum)

Please note, we’re using || operator because we’re looking for true value. checkTree the function will return either true or false and || will pick true if it will be an option.

Now let's execute the function that we’ve just written.

return checkTree(root, targetSum, 0);

Code:

/**
 * 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 = function (root, targetSum) {

    return checkTree(root, targetSum, 0);

    function checkTree(root, targetSum, sum) {
        if (!root) {
            return false;
        }
    
        sum += root.val;
    
        if (root.left === null && root.right === null) {
            return sum === targetSum;
        }
    
        return checkTree(root.left, targetSum, sum) || checkTree(root.right, targetSum, sum)
    };

};

We can write as below also (a common approach)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
  if (!root) return false;
  if (root.val === sum && !root.left && !root.right) return true;
  return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
};

Complexity

Time Complexity
Time complexity will be O(n).

Space Complexity
space complexity should also be O(n).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #112. Path Sum

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!