LeetCode: pathSum

The Problem

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.

What this means is, we are traversing through a tree from root down to a leaf path indicated in blue on the example image below:

The information we know is our input and output here:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

We want to return true if there is a path in our tree that is equivalent to our targetSum. If we do not find that path, we must return false.

The Approach

There are a few ways we can approach this problem, one way is by solving it using good-old recursion.

We first start off by establishing an edge case, we make sure that if the root is null, meaning if there aren't any nodes attached to our root, we must return false.

We then need to add a case where, if our targetSum is found and there are no more children on the left and/or right of the last node, we can return true! Now, what I mean by that is, let's say we have this tree to traverse through:

        7
      /   \
     4      8
    / \    
   3  10

Output: 14

As you can see, from the root that is 7, when we traverse to the left of that tree, we can see that it adds up to 14. 3 is our last node child so we can return true. However, if 3 had other children to traverse through, this would be considered a false path because we need to traverse through the whole path and add that up to 14!

Lastly, what we want to do next is recursively call our left or right children if we are not at the last node child in the tree. Basically, keep moving down the path until we are at the final node.

The Code

var hasPathSum = function(root, targetSum) {
    if(root === null) {
        return false 
    }

    if(root.left == null && root.right == null && targetSum == root.val) return true

    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
};

Refrences

Here is a youtube video that better explains how to approach this algorithm!

pathSum

Thank you for taking the time to read this blog! Please leave any comments, other ways to approach this code challenge, or any advice for other junior developers to benefit from :)
-- Happy Coding <3