Equal Subtree Sums

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given a binary tree where each node contains an integer value. Your task is to count the number of nodes in the tree that satisfy a specific property: the sum of all node values in the node's left subtree must be equal to the node's own value, AND the sum of all node values in its right subtree must also be equal to the node's own value.

Definitions:

The sum of an empty subtree (i.e., if a child is null) is considered to be 0.

A leaf node has a left subtree sum of 0 and a right subtree sum of 0.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of nodes in the level-order representation of the tree.

The second line contains N space-separated integers, representing the tree in level-order format. A value of -1 indicates a null node.

Output Format:

Print a single integer representing the total count of nodes that satisfy the property.

Note:

To solve this efficiently, a single traversal of the tree is required. A post-order traversal (DFS) is ideal. A recursive function can calculate the sum of a subtree and, after receiving the sums from its children, perform the check for the current node.

Sample Input 1:

7
10 6 3 4 0 7 0

Sample Output 1:

Explanation for Sample 1:

Leaf 4: 4!=0. No.
Leaf 7: 7!=0. No.
Node 6: Left sum = 4, Right sum = 0. 6!=4. No.
Node 3: Left sum = 7, Right sum = 0. 3!=7. No.
Root 10: Left sum = 6+4=10, Right sum = 3+7=10. 10==10 and 10==10. Yes. (Count=1).

Sample Input 2:

4
0 0 0

Sample Output 2:

Explanation for Sample 2:

All three leaf nodes are 0. For each leaf, the left and right subtree sums are 0. 0==0, so all three satisfy the condition.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

0 <= N <= 10^5
-1000 <= Node Value <= 1000
The total sum of any subtree will fit within a 64-bit integer type (long in Java, long long in C++).

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Equal Subtree Sums

Console