Frontend School

Sum of Products in Category Tree

DSA
easy

Sum of Products in Category Tree

Easy
Tree Traversal
Binary Tree
Recursion
DFS
BFS

Overview

At Nykaa, our extensive product catalog is often organized hierarchically into categories and subcategories. To understand the total inventory footprint, it's crucial to aggregate product counts across these structures. This problem simulates a simplified version of our category management system, represented as a binary tree.

What you need to do / Task

You are given the root of a binary tree. Each node in this tree has an integer value, node.val, representing the number of unique products directly associated with that specific category. Your task is to calculate the total number of unique products across all categories represented in the entire tree.

Input & output

Input:

  • root: The root node of a binary tree. Each node.val is a non-negative integer.

Output:

  • An integer representing the sum of all node.val values in the tree.

Clarifications

  • Empty Tree: If the root is null, it means there are no categories, and thus no products. In this case, the total sum should be 0.
  • Node Values: Node values (node.val) will always be non-negative.

Examples

1

Example 1

Input:

root = [10,5,15,null,null,12,20]

Output:

62

Note:

The sum of all node values is 10 (root) + 5 (left child) + 15 (right child) + 12 (right-left grandchild) + 20 (right-right grandchild) = 62.

2

Example 2

Input:

root = [1]

Output:

1

Note:

The tree has only one node with value 1, so the total sum is 1.

3

Example 3

Input:

root = []

Output:

0

Note:

The tree is empty (root is null), so the total sum of products is 0.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is between 0 and 10^4.
  • 0 <= Node.val <= 1000.
  • The tree structure will be valid (no cycles, proper binary tree).
  • Standard binary tree node definition: left and right pointers for child nodes.

Out of scope

  • Optimizing for extremely deep trees that might cause stack overflow with recursive solutions (assume typical call stack limits are sufficient for 10^4 nodes).
  • Handling negative product counts (already constrained to non-negative).

What interviewers evaluate

  • Correctness: The solution must accurately sum all node values in the tree.
  • Efficiency: The solution should traverse the tree efficiently, visiting each node exactly once.
  • Code Structure: Clean, readable, and well-organized code.
  • Tree Traversal Understanding: Demonstrating fundamental knowledge of binary tree traversal techniques (e.g., DFS or BFS).

Loading editor...