# Tree — Path Sum

(Easy)

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.

**Note:** A leaf is a node with no children.

**Example:**

Given the below binary tree and `sum = 22`

,

** 5**

**/** \

**4** 8

**/** / \

**11** 13 4

/ **\** \

7 **2** 1

return true, as there exist a root-to-leaf path `5->4->11->2`

which sum is 22.

**Solution:**

Solution is exactly like this algorithm. Try and understand the iterative part.

https://takeitoutamber.medium.com/bst-sum-root-to-leaf-numbers-a8f64e3d9ba1

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def hasPathSum(self, root: TreeNode, sum: int) -> bool:

sum_to_end = 0

stack = [(root, 0)]

found = False

while stack and not found:

node, current_value = stack.pop()

if node:

current_value = current_value + node.val

if not node.left and not node.right:

if current_value == sum:

found = True

current_value = 0else:

stack.append((node.left, current_value))

stack.append((node.right, current_value))

return found