Frontend School

Calculate Total Value of Deepest Product Categories

DSA
easy

Calculate Total Value of Deepest Product Categories

Easy
Tree
Binary Tree
Depth-First Search
Breadth-First Search

Overview

Meesho's product catalog is structured hierarchically, often represented as a tree where nodes represent categories or subcategories, and their values could represent aggregated metrics like 'total product count' or 'estimated market value'. Efficiently navigating and extracting insights from this structure is crucial for category managers. For instance, understanding the aggregated value of the most granular (deepest) categories can inform strategic decisions about inventory, pricing, or new product launches.

What you need to do / Task

You are tasked with writing a function that, given the root of a binary tree representing a product category hierarchy, calculates the sum of the values of all nodes that are at the maximum depth of the tree.

Input & output

Your function sumOfNodesAtMaxDepth will accept one parameter:

  • root: A TreeNode object representing the root of the binary tree. Each TreeNode has an integer val and optional left and right child pointers.

The function should return an integer, which is the sum of val for all nodes located at the deepest level of the tree.

TreeNode Definition:

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

Clarifications

  • Empty Tree: If the root is null (an empty tree), what should be returned? In this case, there are no nodes, so the sum should be 0.
  • Single Node Tree: If the tree consists of only the root node, its value should be returned. The depth of a single node tree is 0.
  • Node Values: Node values can be positive, negative, or zero.

Examples

1

Example 1

Input:

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

Output:

7

Note:

The deepest level has nodes with value [7]. Their sum is 7.

2

Example 2

Input:

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

Output:

9

Note:

The deepest level has nodes with values [4, 5]. Their sum is 4 + 5 = 9.

3

Example 3

Input:

root = [1]

Output:

1

Note:

The deepest level has node with value [1]. Their sum is 1.

4

Example 4

Input:

root = null

Output:

0

Note:

An empty tree has no nodes, so the sum is 0.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is between 0 and 10^4.
  • Node values (val) are between -1000 and 1000.
  • The depth of the tree will not exceed 1000.
  • The input tree is a valid binary tree.

Out of scope

  • Input validation (e.g., handling non-integer values, cyclic structures). Assume the input always conforms to the TreeNode definition and constraints.
  • Performance optimization beyond typical time/space complexity for tree traversals.

What interviewers evaluate

  • Correctness: Does the solution correctly calculate the sum for all valid tree structures, including edge cases?
  • Efficiency: Is the solution optimal in terms of time and space complexity for traversing the tree?
  • Code Clarity: Is the code well-structured, readable, and easy to understand?
  • Edge Case Handling: Does the solution gracefully handle cases like an empty tree or a single-node tree?

Loading editor...