Teaching Kids Programming – Count Nodes Equal to Sum of Descendants (Recursive Depth First Search Algorithm)


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary tree, return the number of nodes where the value of the node is equal to the sum of the values of its descendants. A descendant of a node x is any node that is on the path from node x to some leaf node. The sum is considered to be 0 if the node has no descendants.

count-nodes-equal-to-sum-of-descendants Teaching Kids Programming - Count Nodes Equal to Sum of Descendants (Recursive Depth First Search Algorithm) algorithms Depth First Search python Recursion teaching kids programming youtube video

Count Nodes Equal to Sum of Descendants

Example 1:
Input: root = [10,3,4,2,1]
Output: 2
Explanation:
For the node with value 10: The sum of its descendants is 3+4+2+1 = 10.
For the node with value 3: The sum of its descendants is 2+1 = 3.

Example 2:
Input: root = [2,3,null,2,null]
Output: 0
Explanation:
No node has a value that is equal to the sum of its descendants.

Example 3:
Input: root = [0]
Output: 1
For the node with value 0: The sum of its descendants is 0 since it has no descendants.

Constraints:
The number of nodes in the tree is in the range [1, 105].
0 <= Node.val <= 10^5

Hints:
Can we reuse previously calculated information?
How can we calculate the sum of the current subtree using the sum of the child’s subtree?

Count Nodes Equal to Sum of Descendants (Recursive Depth First Search Algorithm)

This is similar to Day 490: Teaching Kids Programming – Count Nodes Equal to Average of Subtree via Recursive Depth First Search Algorithm where we can perform a Depth First Search Algorithm to traverse the binary tree, and for each node, we need to return the sum of left tree and right tree respectively. At this time, we check if the sum of left and right tree is equal to the current root, we increment the counter.

The DFS can be easily implemented via Recursion. And also we can implement it in iterative manner via using a stack. The time complexity is O(N) as each node needs to be visited once. And the space complexity is O(H) and in worse case when the tree is degraded to a linked-list (or each node has only one child), the O(H)=O(N).

The Recursive Depth First Search is a bottom-up manner, where when we reach the leaf nodes, we walk backwards/upwards to compute the sum of the ancestor nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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 equalToDescendants(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        
        def dfs(root):
            if not root:
                return 0
            
            lsum = dfs(root.left)
            rsum = dfs(root.right)
            
            if lsum + rsum == root.val:
                self.ans += 1
            return lsum + rsum + root.val
        
        dfs(root)
        return self.ans
# 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 equalToDescendants(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        
        def dfs(root):
            if not root:
                return 0
            
            lsum = dfs(root.left)
            rsum = dfs(root.right)
            
            if lsum + rsum == root.val:
                self.ans += 1
            return lsum + rsum + root.val
        
        dfs(root)
        return self.ans

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
a WordPress rating system
682 words
Last Post: Teaching Kids Programming - How to Design a Random Sudoku? Algorithm to Design a Random Sudoku
Next Post: Teaching Kids Programming - Algorithms to Find Minimum Common Value of Two Sorted Arrays (Binary Search, Two Pointer, Brute Force, Hash Set Intersection)

The Permanent URL is: Teaching Kids Programming – Count Nodes Equal to Sum of Descendants (Recursive Depth First Search Algorithm)

Leave a Reply