8.01.2024
938. Range Sum of BST easy
blog post
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 rangeSpace 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