Jobs

Interviews

Discussions

Count Nodes Equal to Sum of Descendants

Medium

Asked by:

13 views

Topics:

TreesRecursion

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, meaning that the descendant is either x itself, or one of its children (not necessarily direct children), or one of its children's children and so on.

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
Explanation:
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, 10⁵].
0 <= Node.val <= 10⁵

Try coding it in LeetCode

Count Nodes Equal to Sum of Descendants

Medium

Asked by:

13 views

Topics:

TreesRecursion

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.

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
Explanation:
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, 10⁵].
0 <= Node.val <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the node data? Can they be negative, zero, or floating-point numbers?
Is the input tree guaranteed to be a binary tree, or can nodes have more than two children?
If a node has a value equal to the sum of its descendants, but some of its descendants are null, do we still count it?
What should I return if the root is null or the tree is empty?
Should I consider the node itself as part of its descendants' sum when calculating the sum?

Brute Force Solution

Approach

The brute force method for this tree problem involves checking every single node to see if it meets our condition. We'll calculate the sum of all nodes beneath a given node, and then compare that sum to the value of the node itself.

Here's how the algorithm would work step-by-step:

Start by looking at the very top node of the tree.
For that top node, find all the nodes that are below it, tracing every possible path downwards.
Add up the values of all those nodes below the top node. This is the sum of its descendants.
Check if the value of the top node is equal to that sum you just calculated.
If it is, add one to a counter that keeps track of how many nodes meet our condition.
Now, move on to the next node in the tree. It could be any node. Do the exact same steps as before: find all nodes below it, add up their values, and check if that sum equals the node's value.
Keep repeating this process for every single node in the tree, no matter where it is located.
After you've checked every node, the counter will hold the total number of nodes that are equal to the sum of their descendants.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def count_nodes_equal_to_sum_of_descendants(root):
    nodes_that_meet_condition = 0

    def get_sum_of_descendants(node):
        if not node:
            return 0

        sum_of_descendants_left = get_sum_of_descendants(node.left)
        sum_of_descendants_right = get_sum_of_descendants(node.right)

        return node.data + sum_of_descendants_left + sum_of_descendants_right

    def traverse_tree(node):
        nonlocal nodes_that_meet_condition

        if not node:
            return

        # Sum all descendants
        sum_of_descendants = get_sum_of_descendants(node) - node.data

        # Check if meets the condition
        if node.data == sum_of_descendants:
            # Increment the counter
            nodes_that_meet_condition += 1

        traverse_tree(node.left)

        # Visit right subtree
        traverse_tree(node.right)

    # Need to start traversal from the root node
    traverse_tree(root)

    return nodes_that_meet_condition

Big(O) Analysis

Time Complexity

O(n²) – The brute force method visits each of the n nodes in the tree. For each node, it calculates the sum of its descendants by traversing the subtree rooted at that node. In the worst-case scenario (e.g., a skewed tree), calculating the sum of descendants for a given node might require visiting all the remaining nodes in the tree. Therefore, for each of the n nodes, we potentially perform O(n) work to calculate the sum of its descendants. This leads to a total time complexity of O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach, as described, involves recursively traversing the tree to calculate the sum of descendants for each node. In the worst-case scenario (e.g., a skewed tree), the recursion depth can be equal to the number of nodes, N, in the tree. Each recursive call adds a new frame to the call stack, leading to a space complexity proportional to the maximum depth of the recursion. Therefore, the auxiliary space used by the recursion stack is O(N).

Optimal Solution

Approach

The most efficient way to solve this involves a method where each part of the tree calculates its contribution to the solution. By computing sums from the bottom up, we avoid redundant calculations and quickly identify the nodes that meet the criteria.

Here's how the algorithm would work step-by-step:

Start at the bottom of the tree, at the leaves (the nodes with no children).
For each node, determine the sum of its descendants. Since leaf nodes have no descendants, their descendant sum is zero.
Move upwards, calculating the descendant sum for each node as the sum of its children's descendant sums, plus the values of the children themselves.
While calculating these sums, also check if the value of a node is equal to the descendant sum you just calculated for it.
Keep track of how many nodes satisfy this condition.
After processing the entire tree, the final count will be the answer.

Code Implementation

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def count_nodes_equal_to_sum_of_descendants(root):
    nodes_equal_to_descendants = 0

    def calculate_descendant_sum(node):
        nonlocal nodes_equal_to_descendants

        if not node:
            return 0

        # Recursively calculate the sum of descendants for left and right subtrees.
        left_descendant_sum = calculate_descendant_sum(node.left)

        right_descendant_sum = calculate_descendant_sum(node.right)

        # Descendant sum includes values of the children.
        descendant_sum = left_descendant_sum + right_descendant_sum

        if node.left:
            descendant_sum += node.left.value

        if node.right:
            descendant_sum += node.right.value

        # Check if current node's value is equal to the descendant sum.
        if node.value == descendant_sum:
            nodes_equal_to_descendants += 1

        return descendant_sum

    calculate_descendant_sum(root)
    return nodes_equal_to_descendants

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once to compute the descendant sum and check the condition. The number of nodes in the tree is represented by 'n'. At each node, a constant amount of work is performed: calculating the sum of the children's descendant sums and comparing it with the node's value. Since each node is visited only once and the work at each node is constant, the overall time complexity is directly proportional to the number of nodes.

Space Complexity

O(H) – The primary driver of auxiliary space complexity is the recursion depth during the tree traversal. In the worst-case scenario, where the tree is highly skewed (e.g., a linked list), the recursion depth can reach N, where N is the number of nodes in the tree. However, we often consider the height (H) of the tree as the limiting factor for recursion, as that determines the maximum number of stack frames used during the recursive calls. Thus, the maximum space occupied by the call stack is proportional to the height of the tree, H. Hence, the auxiliary space complexity is O(H).

Edge Cases

Case	How to Handle
Null root node	Return 0; the count of nodes is trivially zero for a null tree.
Single node tree	Return 1 since the node's value will equal the sum of its (empty) descendants.
Large tree to test for stack overflow with recursion	Ensure the solution uses techniques like tail recursion optimization or iterative approaches to avoid stack overflow errors with deep trees.
Tree where all nodes have the same value	Handle it normally as the sum of the children's descendants will often also match the node's value leading to a valid count.
Tree with negative node values	Ensure the sum calculation correctly handles negative values; no special handling is required if using addition.
Tree with very large positive node values that can cause integer overflow in the sum calculation	Use a data type like long or BigInteger to store intermediate sums to prevent integer overflow.
A skewed tree where the sum of descendants of root is not fitting in integer range.	Use long integer to store sum, check if that sum equals the root value and count accordingly.
Tree where root node value is 0 and all descendants are also 0	This case needs no special handling and is correctly calculated.

Null root node

How to Handle:

Return 0; the count of nodes is trivially zero for a null tree.

Single node tree

How to Handle:

Return 1 since the node's value will equal the sum of its (empty) descendants.

Large tree to test for stack overflow with recursion

How to Handle:

Ensure the solution uses techniques like tail recursion optimization or iterative approaches to avoid stack overflow errors with deep trees.

Tree where all nodes have the same value

How to Handle:

Handle it normally as the sum of the children's descendants will often also match the node's value leading to a valid count.

Tree with negative node values

How to Handle:

Ensure the sum calculation correctly handles negative values; no special handling is required if using addition.

Tree with very large positive node values that can cause integer overflow in the sum calculation

How to Handle:

Use a data type like long or BigInteger to store intermediate sums to prevent integer overflow.

A skewed tree where the sum of descendants of root is not fitting in integer range.

How to Handle:

Use long integer to store sum, check if that sum equals the root value and count accordingly.

Tree where root node value is 0 and all descendants are also 0

How to Handle:

This case needs no special handling and is correctly calculated.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the node data? Can they be negative, zero, or floating-point numbers?
Is the input tree guaranteed to be a binary tree, or can nodes have more than two children?
If a node has a value equal to the sum of its descendants, but some of its descendants are null, do we still count it?
What should I return if the root is null or the tree is empty?
Should I consider the node itself as part of its descendants' sum when calculating the sum?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very top node of the tree.
For that top node, find all the nodes that are below it, tracing every possible path downwards.
Add up the values of all those nodes below the top node. This is the sum of its descendants.
Check if the value of the top node is equal to that sum you just calculated.
If it is, add one to a counter that keeps track of how many nodes meet our condition.
Now, move on to the next node in the tree. It could be any node. Do the exact same steps as before: find all nodes below it, add up their values, and check if that sum equals the node's value.
Keep repeating this process for every single node in the tree, no matter where it is located.
After you've checked every node, the counter will hold the total number of nodes that are equal to the sum of their descendants.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def count_nodes_equal_to_sum_of_descendants(root):
    nodes_that_meet_condition = 0

    def get_sum_of_descendants(node):
        if not node:
            return 0

        sum_of_descendants_left = get_sum_of_descendants(node.left)
        sum_of_descendants_right = get_sum_of_descendants(node.right)

        return node.data + sum_of_descendants_left + sum_of_descendants_right

    def traverse_tree(node):
        nonlocal nodes_that_meet_condition

        if not node:
            return

        # Sum all descendants
        sum_of_descendants = get_sum_of_descendants(node) - node.data

        # Check if meets the condition
        if node.data == sum_of_descendants:
            # Increment the counter
            nodes_that_meet_condition += 1

        traverse_tree(node.left)

        # Visit right subtree
        traverse_tree(node.right)

    # Need to start traversal from the root node
    traverse_tree(root)

    return nodes_that_meet_condition

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the bottom of the tree, at the leaves (the nodes with no children).
For each node, determine the sum of its descendants. Since leaf nodes have no descendants, their descendant sum is zero.
Move upwards, calculating the descendant sum for each node as the sum of its children's descendant sums, plus the values of the children themselves.
While calculating these sums, also check if the value of a node is equal to the descendant sum you just calculated for it.
Keep track of how many nodes satisfy this condition.
After processing the entire tree, the final count will be the answer.

Code Implementation

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def count_nodes_equal_to_sum_of_descendants(root):
    nodes_equal_to_descendants = 0

    def calculate_descendant_sum(node):
        nonlocal nodes_equal_to_descendants

        if not node:
            return 0

        # Recursively calculate the sum of descendants for left and right subtrees.
        left_descendant_sum = calculate_descendant_sum(node.left)

        right_descendant_sum = calculate_descendant_sum(node.right)

        # Descendant sum includes values of the children.
        descendant_sum = left_descendant_sum + right_descendant_sum

        if node.left:
            descendant_sum += node.left.value

        if node.right:
            descendant_sum += node.right.value

        # Check if current node's value is equal to the descendant sum.
        if node.value == descendant_sum:
            nodes_equal_to_descendants += 1

        return descendant_sum

    calculate_descendant_sum(root)
    return nodes_equal_to_descendants

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return 0; the count of nodes is trivially zero for a null tree.
Single node tree	Return 1 since the node's value will equal the sum of its (empty) descendants.
Large tree to test for stack overflow with recursion	Ensure the solution uses techniques like tail recursion optimization or iterative approaches to avoid stack overflow errors with deep trees.
Tree where all nodes have the same value	Handle it normally as the sum of the children's descendants will often also match the node's value leading to a valid count.
Tree with negative node values	Ensure the sum calculation correctly handles negative values; no special handling is required if using addition.
Tree with very large positive node values that can cause integer overflow in the sum calculation	Use a data type like long or BigInteger to store intermediate sums to prevent integer overflow.
A skewed tree where the sum of descendants of root is not fitting in integer range.	Use long integer to store sum, check if that sum equals the root value and count accordingly.
Tree where root node value is 0 and all descendants are also 0	This case needs no special handling and is correctly calculated.

Null root node

How to Handle:

Return 0; the count of nodes is trivially zero for a null tree.

Single node tree

How to Handle:

Return 1 since the node's value will equal the sum of its (empty) descendants.

Large tree to test for stack overflow with recursion

How to Handle:

Ensure the solution uses techniques like tail recursion optimization or iterative approaches to avoid stack overflow errors with deep trees.

Tree where all nodes have the same value

How to Handle:

Handle it normally as the sum of the children's descendants will often also match the node's value leading to a valid count.

Tree with negative node values

How to Handle:

Ensure the sum calculation correctly handles negative values; no special handling is required if using addition.

Tree with very large positive node values that can cause integer overflow in the sum calculation

How to Handle:

Use a data type like long or BigInteger to store intermediate sums to prevent integer overflow.

A skewed tree where the sum of descendants of root is not fitting in integer range.

How to Handle:

Use long integer to store sum, check if that sum equals the root value and count accordingly.

Tree where root node value is 0 and all descendants are also 0

How to Handle:

This case needs no special handling and is correctly calculated.