Teaching Kids Programming – Finding Path Sum in Binary Tree via Breadth First Search Algorithm (and Iterative DFS)

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.

Finding Path Sum in a Binary Tree

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.

–EOF (The Ultimate Computing & Technology Blog) —