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

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

We can solve this problem via Depth First Search Algorithm or Breadth First Search Algorithm: Teaching Kids Programming – Finding Path Sum in Binary Tree via Breadth First Search Algorithm

Finding Path Sum in Binary Tree via Recursive Depth First Search Algorithm

We can traverse the binary tree via Depth First Search Algorithm. We need to carry the sum (either remaining sum or accumulated sum) when we visit the nodes. The DFS can be easily implemented (trivial) via Recursion, although in the next lession, we’ll show how to do this using a manual stack (similar to Breadth First Search).

See following Python implementation of Recursive Depth First Search, we can pass the current updated sum when we call the Recursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        def dfs(root, s):
            if not root:
                return False
            if root.left == root.right:
                return s == 0
            for k in (root.left, root.right):
                if k and dfs(k, s - k.val):
                    return True
            return False
        
        return dfs(root, targetSum - root.val)

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        def dfs(root, s):
            if not root:
                return False
            if root.left == root.right:
                return s == 0
            for k in (root.left, root.right):
                if k and dfs(k, s - k.val):
                    return True
            return False
        
        return dfs(root, targetSum - root.val)

Alternatively, we can handle the sum in the Recursion call.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(root, s):
            if not root:
                return False
            s += root.val
            if s == targetSum and root.left == root.right:
                return True
            return dfs(root.left, s) or dfs(root.right, s)
        
        return dfs(root, 0)

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(root, s):
            if not root:
                return False
            s += root.val
            if s == targetSum and root.left == root.right:
                return True
            return dfs(root.left, s) or dfs(root.right, s)
        
        return dfs(root, 0)

Both DFS implementations run at O(N) time and O(H) space. N is the number of the nodes in the given binary tree and the H is the height of the binary tree. In the worst case, H=N when each node in binary tree has only one child or O(LogN) when the given binary tree is highly balance: the different between any child nodes is no more than one.

–EOF (The Ultimate Computing & Technology Blog) —