We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Nodes Equal to Sum of Descendants

Number: 2126

Difficulty: Medium

Paid? Yes

Companies: Meta

Problem Description

Given the root of a binary tree, return the number of nodes where the node's value is equal to the sum of the values of its descendants. A descendant is any node on the path from the current node down to a leaf. For a node with no descendants, the descendant sum is considered to be 0.

Key Insights

  • Use a postorder traversal (depth-first search) to compute the sum of each subtree.
  • For each node, compare its value with the sum of its descendants (left subtree sum + right subtree sum).
  • Leaf nodes have a descendant sum of 0, so count them if their value is 0.
  • Use recursion to both compute subtree sums and update the count in a single DFS pass.

Space and Time Complexity

Time Complexity: O(n) – Each node is visited once. Space Complexity: O(h) – Recursive call stack, where h is the height of the tree.

Solution

Perform a postorder DFS to calculate the sum of values for each subtree. For every node:

  1. Recursively get the sum of the left subtree.
  2. Recursively get the sum of the right subtree.
  3. Check if the node's value equals the sum of its descendants (left sum + right sum).
  4. Increment a counter if the condition is met.
  5. Return the total sum of the subtree rooted at that node (node's value + left sum + right sum).

This approach efficiently computes the required sums and counts matching nodes in one pass.

Code Solutions

# Define the structure for a tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val            # The value of the node.
        self.left = left          # Pointer to the left child.
        self.right = right        # Pointer to the right child.

class Solution:
    def equalToDescendants(self, root: TreeNode) -> int:
        self.count = 0  # Initialize counter for nodes meeting the condition.
        
        def dfs(node):
            # Base condition: If the node is None, return sum as 0.
            if not node:
                return 0
            # Recursively compute the sum of the left subtree.
            left_sum = dfs(node.left)
            # Recursively compute the sum of the right subtree.
            right_sum = dfs(node.right)
            # If the node's value equals the sum of its descendants, increment count.
            if node.val == left_sum + right_sum:
                self.count += 1
            # Return the total sum of the subtree rooted at this node.
            return node.val + left_sum + right_sum
        
        dfs(root)  # Start DFS from the root.
        return self.count  # Return the final count.
← Back to All Questions