Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Example:

      5
     / \
    4   8
   /   / \
  11  13  4  sum=20

Output: true

Approach

Java

public class PathSum {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(5);
        tree.left = new TreeNode(4);
        tree.left.left = new TreeNode(11);
        tree.right = new TreeNode(8);
        tree.right.left = new TreeNode(13);
        tree.right.right = new TreeNode(4);
        int sum = 20;
        System.out.println(hasPathSum(tree, sum));
    }

    // function to check if their is
    // a path from root to leaf with
    // given sum
    private static boolean hasPathSum(TreeNode root, int sum) {

        if (root == null && sum >= 0)
            return false;
        else {
            boolean ans = false;
            int subsum = sum - root.val;
            if (subsum == 0 && root.left == null && root.right == null)
                return true;
            if (root.left != null)
                ans = ans || hasPathSum(root.left, subsum);
            if (root.right != null)
                ans = ans || hasPathSum(root.right, subsum);
            return ans;
        }
    }
}

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

C++

#include <bits/stdc++.h>
using namespace std;


//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};


//function to check if their is
//a path from root to leaf with
//given sum
bool hasPathSum(TreeNode* root, int sum)
{
        if(root==NULL &&sum>=0)
               return false;
        else
        {
         bool ans=false;
        int subsum=sum-root->data;
        if(subsum==0&&root->left==NULL&&root->right==NULL)
               return true;
        if(root->left)
               ans=ans||hasPathSum(root->left,subsum);
        if(root->right)
                ans=ans||hasPathSum(root->right,subsum);
        return ans;
        }
}
int main()
{
    TreeNode *root=new TreeNode(5);
    root->left=new TreeNode(4);
    root->right=new TreeNode(8);
    root->left->left=new TreeNode(11);
    root->right->left=new TreeNode(13);
    root->right->right=new TreeNode(4);
    int sum=20;
    if(hasPathSum(root,sum))
      cout<<"true";
    else
     cout<<"false";
     return 0;
    
}