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

**Teaching Kids Programming**: Videos on **Data Structures and Algorithms**

https://www.youtube.com/watch?v=8RVb2vO3zo4

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: falseExplanation: 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.

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

713 words

**Last Post**: Teaching Kids Programming – Finding Path Sum in Binary Tree via Recursive Depth First Search Algorithm

Source: Internet