Problem 938

(Last updated: )

Question statement:

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Solution

A binary tree is a tree where each node (parent) has at most two associated (sub-)nodes (children). A binary search tree is a data structure where each node has a value (obtained from a poset) and the left child has value $\leq$ than the parent node, and the right child has value $\geq$ the parent node.

Main idea:

Have a sum variable initialized to zero, and whenever we encounter a node satisfying \texttt{low $\leq$ node.val $\leq$ high}$, we add node.val to sum. If on the other hand, $\texttt{node.val $>$ high}, then simply pass to the left sub-tree (and recurse until condition 1 is satisfied). Similarly if $\texttt{node.val $<$ low}$, then simply pass to the right sub-tree (and recurse until condition 1 is satisfied).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def helper(self, root, low, high, counter):
    if(root == None):
        return 0
    if(root.val > high):
        return self.helper(root.left, low, high, counter)
    elif(root.val < low):
        return self.helper(root.right, low, high, counter)
    else:
        counter += root.val + self.helper(root.right, low, high, counter) + self.helper(root.left, low, high, counter)
        return counter

def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
    sum = self.helper(root, low, high, 0)
    return sum

Comments:

Time complexity: O(n) where n is the number of nodes in the BST

The above code runs in 123ms beats 87.91% of users. It uses 24.48MB of memory, beating 86.73% of users.