# Teaching Kids Programming – Finding Path Sum in Binary Tree via Breadth First Search Algorithm

Teaching Kids Programming – Finding Path Sum in Binary Tree via Breadth First Search Algorithm | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:
Input: root = [1,2,3], targetSum = 5
Output: false

Explanation: There two root-to-leaf paths in the tree:
(1 — 2): The sum is 3.
(1 — 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Traversing a Binary Tree (or a Graph) can be done via (Recursive) Depth First Search Algorithm (DFS – Teaching Kids Programming – Finding Path Sum in Binary Tree via Recursive Depth First Search Algorithm) or Breadth First Search Algorithm (BFS).

### Finding Path Sum in Binary Tree via Breadth First Search Algorithm

We can use a Queue (First In First Out) to implement a Breadth First Search (BFS) – which traverses the binary tree in level-by-level order. The time/space complexity for BFS is O(N) where N is the number of the nodes in a given binary tree.

We need to store the node as well as the remaining sum in the queue. And if a node is a leaf node and the remaining sum is zero, we’ve just found a path. Another way is to keep tracking of the accumulated sum (which initially is zero), and then once we reach the leaf node with the target sum, we have found a path.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ``` ```class Solution:     def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:         if not root:             return False                 q = deque([(root, targetSum - root.val)])         while q:             cur, curSum = q.popleft()             if cur.left is None and cur.right is None and curSum == 0:                 return True             if cur.left:                 q.append((cur.left, curSum - cur.left.val))             if cur.right:                 q.append((cur.right, curSum - cur.right.val))         return False```
```class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False

q = deque([(root, targetSum - root.val)])
while q:
cur, curSum = q.popleft()
if cur.left is None and cur.right is None and curSum == 0:
return True
if cur.left:
q.append((cur.left, curSum - cur.left.val))
if cur.right:
q.append((cur.right, curSum - cur.right.val))
return False```

If we change the deque to stack, or simply we use pop instead of popleft, it will sort-of become a Iterative Depth First Search. If we push the left and then right node to the stack, the order of traversing will be NRL which is reverse pre-order.

If we push the right, and then left node to the stack, the order of traversing the binary tree will be NLR which is Pre-order.

GD Star Rating