LeetCode Entry

938. Range Sum of BST

8.01.2024 easy 2024 kotlin

Sum of BST in range [low..high].

938. Range Sum of BST easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/465

Problem TLDR

Sum of BST in range [low..high].

Intuition

Let’s iterate it using a Depth-First Search and check if each value is in the range.

Approach

  • Careful: if the current node is out of range, we still must visit its children.
  • However, we can prune visit on the one side

Complexity

  • Time complexity: \(O(r)\), r is a range

  • Space complexity: \(O(log(n))\)

Code


  fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int =
   root?.run {
      (if (`val` in low..high) `val` else 0) +
      (if (`val` > low) rangeSumBST(left, low, high) else 0) +
      (if (`val` < high) rangeSumBST(right, low, high) else 0)
    } ?: 0