Leetcode in Scala3 (Dotty): Range Sum of BST
I solve “Range Sum of BST” problem from Leetcode recursively.
Let’s define data structures first:
case class TreeNode(value: Int, left: TreeNode, right: TreeNode)
def empty: TreeNode = null
def leaf(value: Int): TreeNode = TreeNode(value, null, null)
given treeNodeOps: (tn: TreeNode) extended with
def isEmpty: Boolean = tn == null
Then the recursive solution is as follows:
object Solution
// time: O(nodes_count)
// space: O(tree_depth)
def rangeSumBST(root: TreeNode, l: Int, r: Int): Int =
if (root.isEmpty)
0
else
val r1 =
if (l <= root.value && root.value <= r) root.value
else 0
val r2 =
if (root.value > l) rangeSumBST(root.left, l, r)
else 0
val r3 =
if (root.value < r) rangeSumBST(root.right, l, r)
else 0
r1 + r2 + r3
The simple test:
@main def main(): Unit =
val tree =
TreeNode(
10,
TreeNode(
5,
leaf(3),
leaf(7)),
TreeNode(
15,
empty,
leaf(18)),
)
assert(Solution.rangeSumBST(tree, 7, 15) == 32)