Frontend School

Sum of Grandchildren of Even-ID Campaigns

DSA
medium

Sum of Grandchildren of Even-ID Campaigns

Medium
Tree
Depth-First Search
Breadth-First Search
Binary Tree

Overview

Inmobi manages a vast and intricate network of ad campaigns, often organized in hierarchical structures. Each node in this hierarchy represents a unique campaign, identified by a numeric ID. Understanding specific relationships within this structure is crucial for targeted analysis and optimization. This problem challenges you to identify and aggregate data based on a particular multi-generational relationship: summing the IDs of campaigns that are 'grandchildren' of campaigns with even numeric IDs.

What you need to do / Task

You are given the root of a binary tree representing an ad campaign hierarchy. Each TreeNode has a val property which is a unique campaign ID. Your task is to implement a function sumGrandchildrenOfEvenIdCampaigns that calculates the sum of val for all nodes that have an even-valued grandparent.

Input & output

Input:

  • root: A TreeNode | null representing the root of the binary tree. Each node has a val (number), left (TreeNode | null), and right (TreeNode | null).

Output:

  • A number representing the total sum of val for all nodes that are grandchildren of an even-ID campaign.

Clarifications

  • An "even-ID campaign" is a node whose val is an even number.
  • A "grandchild" of a node A is a node C such that A is the parent of B, and B is the parent of C.
  • If the root is null, or the tree does not contain any even-ID campaigns with grandchildren, the function should return 0.
  • Node values (val) will be positive integers.

Examples

1

Example 1

Input:

root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Output:

18

Note:

Campaign 6 (even ID) has left child 7 (parent of 2, 7) and right child 8 (parent of 1, 3). Grandchildren of 6 are 2, 7, 1, 3. Campaign 8 (even ID) has left child 1 (parent of 9) and right child 3 (parent of 5). Grandchildren of 8 are 9, 5. Total sum = 2+7+1+3+9+5 = 27. Correction: The provided example array structure implies specific children. For root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]: 6 (even) /
7 8 (even) / \ /
2 7 1 3 /\ /\ /\ /
9 _ 1 4 _ _ 5 Grandchildren of 6: (via 7) -> 2, 7. (via 8) -> 1, 3. Sum = 2+7+1+3 = 13. Grandchildren of 8: (via 1) -> 9. (via 3) -> 5. Sum = 9+5 = 14. Total sum = 13 + 14 = 27. Re-evaluating example. The explanation for the first example is incorrect; let's stick to the tree structure implied by the array and correct the explanation.

2

Example 2

Input:

root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Output:

27

Note:

Campaign 6 (even ID) has grandchildren 2, 7, 1, 3. Campaign 8 (even ID) has grandchildren 9, 5. Total sum = 2+7+1+3+9+5 = 27.

3

Example 3

Input:

root = [2,1,3,4,5,6,7]

Output:

22

Note:

Campaign 2 (even ID) has grandchildren 4, 5, 6, 7. Total sum = 4+5+6+7 = 22.

4

Example 4

Input:

root = [1,2,3,4,5,6,7]

Output:

0

Note:

No campaign with an even ID has any grandchildren in this hierarchy.

Constraints

Constraints & assumptions

  • The number of nodes in the tree will be between 0 and 10^4.
  • Node values (val) will be between 1 and 10^5.
  • The tree structure is a valid binary tree.

Out of scope

  • Handling non-integer or negative node values.
  • Validating the input tree structure (assume it's always valid).
  • Optimizing for extremely deep recursion stack limits (standard call stack depth is sufficient).

What interviewers evaluate

  • Correctness: The solution must correctly identify and sum all eligible grandchildren nodes across various tree structures and edge cases.
  • Efficiency: The solution should traverse the tree efficiently, ideally in a single pass (O(N) time complexity).
  • Code Quality: The code should be clean, readable, well-structured, and demonstrate good programming practices.
  • Problem-Solving: Ability to decompose the problem, choose an appropriate traversal strategy (DFS or BFS), and manage state (parent/grandparent info) effectively.

Loading editor...