Given a binary tree and an integer S, check whether there is root to leaf path with its sum as S.
Example 1:
Input:
Tree = 
            1
          /   \
        2      3
S = 2
Output: 0
Explanation:
There is no root to leaf path with sum 2.
Example 2:
Input:
Tree = 
            1
          /   \
        2      3
S = 4
Output: 1
Explanation:
The sum of path from leaf node 3 to root 1 is 4.
Your Task:  
You dont need to read input or print anything. Complete the function hasPathSum() which takes root node and target sum S as input parameter and returns true if path exists otherwise it returns false.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ N ≤ 10^4
1 ≤ S ≤ 10^6

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self,val):
        self.data = val
        self.left = None
        self.right = None
'''
class Solution:
    def hasPathSum(self,root, S):
        '''
        :param root: root of given tree.
        :param sm: root to leaf sum
        :return: true or false
        '''
        # code here

Solutions:
class Solution:

	def hasPathSum(self, root, S):

		def path(rt, c, s):
			if rt is None:
				return
			if rt.left is None and rt.right is None:
				return s == c + rt.data
			return path(rt.left, c + rt.data, s) or path(rt.right, c + rt.data, s)
		return path(root, 0, S)


class Solution:

	def hasPathSum(self, root, S):

		def fun(root, S):
			sumi = 0
			S = S - root.data
			if root is None:
				return 0
			if root.left is None and root.right is None and (S == 0):
				return 1
			if root.left:
				sumi = sumi or fun(root.left, S)
			if root.right:
				sumi = sumi or fun(root.right, S)
			return sumi
		t = fun(root, S)
		return t


def inorder(root, S, su):
	if root is None:
		return False
	su += root.data
	if su == S and root.left == None and (root.right == None):
		return True
	if inorder(root.left, S, su) or inorder(root.right, S, su):
		return True
	return False

class Solution:

	def hasPathSum(self, root, S):
		su = 0
		return inorder(root, S, su)


def check(root, S, a):
	if root == None:
		return False
	a += root.data
	if a == S and root.left == None and (root.right == None):
		return True
	if check(root.left, S, a) or check(root.right, S, a):
		return True
	return False

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:

	def hasPathSum(self, root, S):
		a = 0
		return check(root, S, a)


def tree(root, S, ans):
	if root == None:
		return False
	ans += root.data
	if ans == S and root.left == None and (root.right == None):
		return True
	if tree(root.left, S, ans) or tree(root.right, S, ans):
		return True
	return False

class Solution:

	def hasPathSum(self, root, S):
		ans = 0
		if tree(root, S, ans):
			return 1
		return 0


class Solution:

	def hasPathSum(self, root, S):
		if root == None:
			return 0
		subsum = S - root.data
		if subsum == 0 and root.left == None and (root.right == None):
			return True
		return self.hasPathSum(root.left, subsum) or self.hasPathSum(root.right, subsum)


class Solution:

	def hasPathSum(self, root, S):

		def dfs(node, currsum):
			if not node:
				return False
			currsum += node.data
			if not node.left and (not node.right):
				return currsum == S
			return dfs(node.left, currsum) or dfs(node.right, currsum)
		return dfs(root, 0)


class Solution:

	def hasPathSum(self, root, S):

		def dfs(root, sumi):
			if root is None:
				return False
			sumi += root.data
			if root.left is None and root.right is None:
				return sumi == S
			return dfs(root.left, sumi) or dfs(root.right, sumi)
		return dfs(root, 0)


class Solution:
	res = 0

	def fun(self, root, s, S):
		if root == None:
			return
		s += root.data
		if s > S:
			return
		if s == S:
			if root.left == None and root.right == None:
				self.res = 1
			else:
				return
		self.fun(root.left, s, S)
		self.fun(root.right, s, S)

	def hasPathSum(self, root, S):
		self.fun(root, 0, S)
		return self.res


class Solution:

	def hasPathSum(self, root, S):
		if root is None:
			return False
		if root.left is None and root.right is None and (root.data == S):
			return True
		else:
			return self.hasPathSum(root.left, S - root.data) or self.hasPathSum(root.right, S - root.data)


class Solution:

	def hasPathSum(self, root, S):

		def dfs(root, s):
			if root == None:
				return False
			if root.left == None and root.right == None:
				if s - root.data == 0:
					return True
				return False
			return dfs(root.left, s - root.data) or dfs(root.right, s - root.data)
		return dfs(root, S)


class Solution:

	def hasPathSum(self, root, S):

		def path(root, currSum):
			if not root:
				return False
			currSum += root.data
			if not root.left and (not root.right) and (currSum == S):
				return True
			return path(root.left, currSum) or path(root.right, currSum)
		return path(root, 0)


class Solution:

	def solve(self, root, S):
		if root == None:
			return False
		if root.left == None and root.right == None:
			S -= root.data
			if S == 0:
				return True
			else:
				return False
		l = self.solve(root.left, S - root.data)
		if l == True:
			return True
		r = self.solve(root.right, S - root.data)
		if r == True:
			return True
		return False

	def hasPathSum(self, root, S):
		return self.solve(root, S)


class Solution:

	def hasPathSum(self, root, S):
		global b
		b = False

		def finder(root, c):
			global b
			if root == None:
				return
			c += root.data
			if c == S and root.left == None and (root.right == None):
				b = True
				return
			if c > S:
				return
			finder(root.left, c)
			finder(root.right, c)
		finder(root, 0)
		return b


class Solution:

	def hasPathSum(self, root, S):

		def helper(root, add):
			if not root:
				return
			add += root.data
			if root.left is None and root.right is None:
				return add == S
			return helper(root.left, add) or helper(root.right, add)
		return helper(root, 0)


class Solution:

	def hasPathSum(self, root, S):

		def rec(root, d):
			if root.left == None and root.right == None:
				if d + root.data == S:
					return True
				return False
			t1 = False
			t2 = False
			if root.left:
				t1 = rec(root.left, d + root.data)
			if root.right:
				t2 = rec(root.right, d + root.data)
			return t1 or t2
		return rec(root, 0)


class Solution:

	def hasPathSum(self, root, S):

		def hasPathSum(node, s):
			ans = 0
			subSum = s - node.data
			if subSum == 0 and node.left == None and (node.right == None):
				return True
			if node.left is not None:
				ans = ans or hasPathSum(node.left, subSum)
			if node.right is not None:
				ans = ans or hasPathSum(node.right, subSum)
			return ans
		return hasPathSum(root, S)


class Solution:

	def hasPathSum(self, node, s):
		if node is None:
			return s == 0
		else:
			ans = 0
			subSum = s - node.data
			if subSum == 0 and node.left == None and (node.right == None):
				return True
			if node.left:
				ans = ans or self.hasPathSum(node.left, subSum)
			if node.right:
				ans = ans or self.hasPathSum(node.right, subSum)
			return ans


class Solution:

	def hasPathSum(self, root, S):

		def helper(root, target, value):
			if not root:
				return False
			if not root.left and (not root.right):
				return target == value + root.data
			return helper(root.left, target, value + root.data) or helper(root.right, target, value + root.data)
		return helper(root, S, 0)


class Solution:

	def solution(self, root, s, arr):
		if root == None:
			return False
		arr += root.data
		if arr == s and root.left is None and (root.right is None):
			return True
		l = self.solution(root.left, s, arr)
		if l:
			return True
		r = self.solution(root.right, s, arr)
		if r:
			return True
		arr -= root.data
		return False

	def hasPathSum(self, root, S):
		if root == None:
			return 1
		arr = 0
		if self.solution(root, S, arr):
			return 1
		return 0


class Solution:

	def hasPathSum(self, root, S):
		if root == None:
			return 0
		if S == root.data and root.left == None and (root.right == None):
			return 1
		return self.hasPathSum(root.left, S - root.data) or self.hasPathSum(root.right, S - root.data)


class Solution:

	def hasPathSum(self, root, S):
		sum = set()

		def dfs(root, sum_):
			if not root:
				return
			sum_ += root.data
			if root.left or root.right:
				dfs(root.left, sum_)
				dfs(root.right, sum_)
			else:
				sum.add(sum_)
		dfs(root, 0)
		if S in sum:
			return True
		return False