Frontend School

Sum of Depths of Nodes with Even Values

DSA
medium

Sum of Depths of Nodes with Even Values

Medium
Tree
DFS
BFS
Binary Tree
Traversal

Overview

In social media platforms like Sharechat, content is often organized hierarchically, be it trending topics, user-generated categories, or content moderation trees. Understanding the 'depth' or 'reach' of certain content types within these structures can be crucial for analytics and feature development. This problem simulates a scenario where we need to quantify the structural importance (depth) of specific content categories, identified by even numerical values, within a hierarchical topic tree.

What you need to do / Task

Implement a function sumEvenNodeDepths that takes the root of a binary tree as input. Your task is to traverse this tree and calculate the sum of the depths of all nodes whose val (value) is an even number. The root node is considered to be at depth 0.

Input & output

  • Input: root - A TreeNode object representing the root of a binary tree. It can be null if the tree is empty.
  • Output: A number representing the total sum of depths of all nodes with even values.

Clarifications

  • The depth of the root node is 0.
  • If the input root is null (an empty tree), the function should return 0.
  • Node values can be positive, negative, or zero. Remember that 0 is considered an even number.

Examples

1

Example 1

Input:

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

Output:

5

Note:

Tree structure: 0 (val=0, depth=0, even) -> sum += 0 /
1 2 (val=2, depth=1, even) -> sum += 1 / \ /
3 4 5 6 (val=4, depth=2, even) -> sum += 2 (val=3) (val=5) (val=6, depth=2, even) -> sum += 2 Even-valued nodes and their depths: Node 0 (depth 0), Node 2 (depth 1), Node 4 (depth 2), Node 6 (depth 2). Total sum = 0 + 1 + 2 + 2 = 5.

2

Example 2

Input:

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

Output:

5

Note:

Tree structure: 1 (val=1, depth=0, odd) /
2 3 (val=2, depth=1, even) -> sum += 1 / \
4 5 6 (val=4, depth=2, even) -> sum += 2 (val=5) (val=6, depth=2, even) -> sum += 2 Even-valued nodes and their depths: Node 2 (depth 1), Node 4 (depth 2), Node 6 (depth 2). Total sum = 1 + 2 + 2 = 5.

3

Example 3

Input:

root = [1,3,5]

Output:

0

Note:

All nodes (1, 3, 5) have odd values. Therefore, no depths are added to the sum, resulting in 0.

Constraints

Constraints & assumptions

  • The number of nodes N in the tree will be between 0 and 10^4.
  • Node values (val) will be between -10^5 and 10^5.
  • The maximum depth of the tree will not exceed 10^4.

Out of scope

  • Error handling for malformed tree structures (e.g., cycles).
  • Performance optimizations beyond standard time/space complexity for tree traversals, such as cache locality or custom memory allocators.

What interviewers evaluate

  • Correctness of the algorithm in identifying and summing depths of even-valued nodes.
  • Proficiency in implementing a robust tree traversal (DFS or BFS) while managing node depth.
  • Ability to handle edge cases like empty trees or trees with no even-valued nodes.
  • Code clarity, organization, and adherence to standard coding practices.

Loading editor...