Count Nodes Equal to Sum of Descendants

Count Nodes Equal to Sum of Descendants

What is this problem about?

Given the root of a binary tree, you need to count the number of nodes where the node's value is exactly equal to the sum of the values of all its descendants. A descendant of a node is any node in its left or right subtrees. If a node has no descendants (a leaf), the sum of its descendants is considered to be 0.

Why is this asked in interviews?

Meta and other top-tier companies use this problem to assess a candidate's mastery of recursive tree traversals. It is a variation of the subtree-sum problem but focuses on the relationship between a node and its children. It tests your ability to manage state during recursion and distinguishes between the value of a node and the sum of its entire subtree.

Algorithmic pattern used

This is solved using Post-order Traversal (DFS). To check the condition for a node, you must first know the sum of its left subtree and right subtree. Each recursive function call should return the total sum of the subtree rooted at that node (which is left_sum + right_sum + node.val). Before returning, you check if node.val == left_sum + right_sum.

Example explanation

Tree:

    10
   /  
  3    4
 / 
2   1

1. Leaf 2: Descendant sum = 0. Node value = 2. No match. Return 2.
2. Leaf 1: Descendant sum = 0. Node value = 1. No match. Return 1.
3. Node 3: Left sum = 2, Right sum = 1. Descendant sum = 3. Node value = 3. Match! Return $3+2+1=6$.
4. Leaf 4: Descendant sum = 0. Node value = 4. No match. Return 4.
5. Root 10: Left sum = 6, Right sum = 4. Descendant sum = 10. Node value = 10. Match! Return $10+6+4=20$. Total count: 2.

Common mistakes candidates make

The most frequent error is confusing the "sum of descendants" with the "sum of the subtree." For the condition check, you only use the children's returned sums. However, for the value you return to the parent, you must include the current node's value. Another mistake is not accounting for negative node values (if applicable), which can make the sums zero or negative.

Interview preparation tip

Always be clear about what your recursive function returns. Is it the answer to the problem, or is it a helper value (like a sum) needed to find the answer? In most tree problems, the function returns a helper value while updating a global or pass-by-reference variable for the final answer.