/**
* 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}
*/
// O(N) time since we visit all the nodes once, O(N) recursive space if unbalanced
var hasPathSum = function(root, targetSum) {
 // We will do DFS down from root to leaf and see if we can reach the target sum
 const dfs = (currentRoot, remainingTarget) => {
   // If there is no root, return false
   if (currentRoot === null) {
     return false;
   }
   
   // If current root is a leaf node and the leaf node's value is equal to the remaining target, we found a path sum
   if (currentRoot.left === null && currentRoot.right === null && currentRoot.val === remainingTarget) {
     return true;
   }
   
   // Check if by going down the left we can find a path sum
   let hasPathSumLeft = false;
   if (currentRoot.left) {
     hasPathSumLeft = dfs(currentRoot.left, remainingTarget - currentRoot.val);
   }
   
   // Check if by going down the right we can find a path sum
   let hasPathSumRight = false;
   if (currentRoot.right) {
     hasPathSumRight = dfs(currentRoot.right, remainingTarget - currentRoot.val);
   }
   
   return hasPathSumLeft || hasPathSumRight;
 };
 
 return dfs(root, targetSum);
};