Frontend School

Sum of Greater or Equal Nodes in BST

DSA
easy

Sum of Greater or Equal Nodes in BST

Easy
Tree
Binary Search Tree
DFS
Traversal

Overview

In Livspace, we manage vast catalogs of products, often organized hierarchically or by attributes that can be ordered (e.g., price, SKU ID, popularity score). Efficiently querying and aggregating data based on such ordered attributes is crucial for analytics and inventory management. This problem simulates a scenario where you need to quickly sum up values of products (nodes) that meet a certain threshold in a sorted structure.

What you need to do / Task

Given the root of a Binary Search Tree (BST) and an integer k, return the sum of all node values in the BST that are greater than or equal to k.

Input & output

  • root: A TreeNode representing the root of a Binary Search Tree. Each TreeNode has an integer val, a left child (which is either another TreeNode or null), and a right child (which is either another TreeNode or null).
  • k: An integer representing the threshold value.
  • Return: An integer, the sum of all node values node.val such that node.val >= k.

Clarifications

  • The BST is guaranteed to be valid.
  • Node values are non-negative.
  • If the tree is empty or no nodes satisfy the condition, the sum should be 0.

Examples

1

Example 1

Input:

root = [4,2,7,1,3,6,9], k = 6

Output:

22

Note:

Nodes with values 7, 6, and 9 are greater than or equal to 6. Their sum is 7 + 6 + 9 = 22.

2

Example 2

Input:

root = [10,5,15,3,7,null,18], k = 10

Output:

43

Note:

Nodes with values 10, 15, and 18 are greater than or equal to 10. Their sum is 10 + 15 + 18 = 43.

3

Example 3

Input:

root = [], k = 5

Output:

0

Note:

The tree is empty, so the sum of nodes is 0.

4

Example 4

Input:

root = [1,null,2], k = 3

Output:

0

Note:

No nodes in the tree have values greater than or equal to 3.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • 0 <= Node.val <= 10^5
  • 0 <= k <= 10^5
  • The given tree is a valid Binary Search Tree.

Out of scope

  • Validating if the input tree is a BST. Assume it's valid.
  • Modifying the BST structure.
  • Handling non-integer node values or k.

What interviewers evaluate

  • Correctness of the algorithm for all valid inputs, including edge cases.
  • Efficient use of BST properties to minimize traversal.
  • Clear, readable, and well-structured code.
  • Ability to explain time and space complexity.

Loading editor...