Path Sum

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr)
            return false;
        if(root->left == nullptr && root->right == nullptr)
            return targetSum - root->val == 0;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        if (root.left == null && root.right == null && targetSum - root.val == 0) {
            return true;
        }
        
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool hasPathSum(struct TreeNode* root, int targetSum){
    if (root == NULL) {
        return false;
    }
    
    if (root->left == NULL && root->right == NULL) {
        return targetSum == root->val;
    }
    
    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == targetSum) {
            return true;
        }
        return HasPathSum(root.left, targetSum - root.val) || HasPathSum(root.right, targetSum - root.val);
    }
}

                                            
/**
 * 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)
 */

var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    
    if (!root.left && !root.right && targetSum === root.val) return true;
    
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) return false;
    
    if (!root.left && !root.right && root.val === targetSum) return true;
    
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @param Integer $targetSum
     * @return Boolean
     */
    function hasPathSum($root, $targetSum) {
        if ($root === null) {
            return false;
        }
        
        if ($root->left === null && $root->right === null) {
            return $targetSum - $root->val === 0;
        }
        
        return $this->hasPathSum($root->left, $targetSum - $root->val) || $this->hasPathSum($root->right, $targetSum - $root->val);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        if root == nil {
            return false
        }
        if root!.left == nil && root!.right == nil {
            return targetSum == root!.val
        }
        
        let newSum = targetSum - root!.val
        return hasPathSum(root!.left, newSum) || hasPathSum(root!.right, newSum)
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    
    if root.Left == nil && root.Right == nil {
        return targetSum == root.Val
    }
    
    return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = 
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def has_path_sum(root, target_sum)
    if root.nil?
        return false
    end
    if root.left.nil? && root.right.nil? && root.val == target_sum
        return true
    end
    return has_path_sum(root.left, target_sum - root.val) || has_path_sum(root.right, target_sum - root.val)
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 * 
 */
object Solution {
    def hasPathSum(root: TreeNode, targetSum: Int): Boolean = {
        if (root == null) false
        else if (root.left == null && root.right == null && targetSum - root.value == 0) true
        else hasPathSum(root.left, targetSum - root.value) || hasPathSum(root.right, targetSum - root.value)
    }
}

                                            
# Definition for a binary tree node.
#
# defmodule TreeNode do
#   @type t :: %__MODULE{
  
  defmodule Solution do
    def has_path_sum(nil, _target_sum), do: false
    def has_path_sum(%TreeNode{val: val, left: nil, right: nil}, target_sum), do: val == target_sum
    def has_path_sum(%TreeNode{val: val, left: left, right: right}, target_sum) do
      has_path_sum(left, target_sum - val) || has_path_sum(right, target_sum - val)
    end
  end

To solve this coding challenge, we need to determine if there exists a root-to-leaf path in a binary tree such that the sum of the values along the path equals a given target sum. Each node on the path contributes to the total sum, and a leaf is defined as a node with no children.

Explanation

The task is to traverse the binary tree starting from the root and to check if there is any path from the root to a leaf that sums up to the target sum. This can effectively be done using a recursive depth-first search (DFS) approach. Here are the detailed steps to achieve this:

Base case checks:

If the root is
null

or the tree is empty, return
false

since no path exists.

Leaf node check:

If the current node is a leaf (i.e., it has no left or right children), check if its value equals the current target sum. If true, return
true

. Otherwise, return
false

.

Recursive step:

If the current node is not a leaf, recursively call the function for its left and right children with the updated target sum (original target sum minus the current node's value).
If any of the recursive calls return
true

, it means a valid path has been found, and we should return
true

. Otherwise, return
false

.

By following these steps, we ensure that we explore all possible root-to-leaf paths until we find one that meets the criteria or exhaust all possibilities.

Pseudocode

Here is the pseudocode with comprehensive comments for our solution:

                                            
Function hasPathSum(node, targetSum):
# Base case: if the node is null, we return false because no path can exist within a null tree.
If node is null:
Return false

# Check if the node is a leaf
If node.left is null AND node.right is null:
# If it is a leaf, check if the node's value is equal to the remaining targetSum
If node.value equals targetSum:
Return true
Else:
Return false

# Recursive call on the left child with updated targetSum
leftHasPath = hasPathSum(node.left, targetSum - node.value)

# Recursive call on the right child with updated targetSum
rightHasPath = hasPathSum(node.right, targetSum - node.value)

# If any of the recursive calls return true, we have found a valid path
Return leftHasPath OR rightHasPath

Step-by-Step Explanation

Initial Function Call:

Begin with the first call to
hasPathSum(root, targetSum)

.
The
root

is the starting node of the binary tree, and
targetSum

is the initial sum we are trying to achieve.

Checking for null root:

If the
root

is
null

, the tree is empty, and there are no paths to check. Therefore, return
false

.

Leaf Node Check:

If the current node (initially the
root

) is a leaf node (i.e., both left and right children are
null

):

Compare the value of the node with the
targetSum

.
If they are equal, return
true

indicating that a valid path has been found.
If they are not equal, return
false

.

Recursive Calls:

For non-leaf nodes:

Make a recursive call to the left child with the updated target sum (
targetSum - node.value

).
Similarly, make another recursive call to the right child with the updated target sum (
targetSum - node.value

).
Store the results of these calls in variables
leftHasPath

and
rightHasPath

respectively.

Result Compilation:

If either
leftHasPath

or
rightHasPath

is
true

, return
true

indicating a valid path exists.
If both are
false

, return
false

as no valid path was found.

By following the above methodology, the problem is efficiently solved using a depth-first search approach, ensuring that all possible paths are checked and the result is accordingly returned.