Algorithmic problems: Range Sum of BST

An Easy category problem which requires a sound understanding of BSTs to solve efficiently. With the seven th problem of the December leetcoding challenge https://leetcode.com/problems/range-sum-of-bst/ I had the opportunity to revisit tree traversal and various other tree concepts. Frankly speaking, I still trip up on recursive techniques and tree problems as the code to implement tree logic seem unintuitive to me. Nonetheless, let's try our best to understand and solve the problem.

Problem breakdown

We are given the head of a binary search tree and an interval [low, high] our task is to return the sum of all node values which fall inside the range. It is paramount that we understand the nuances of a BST while solving this as we can leverage it to cut our algorithm runtime considerably to that if we used plain tree traversal techniques namely inOrder , preOrder and postOrder .

My approach

Recall that, a BST maintains an interesting property. Given a node of a BST the left node must be less than the root and the right node is greater than the root node. As an extension the left subtree s always less than the root and the right subtree is always greater than the root.

We will use this information to efficiently search for elements that are within the given range and inclusive. As a rough pseudocode, we will

• maintain a total counter variable to calculate the sum

• choose any of the tree traversal techniques, let's go with post-order

• at each iteration, we will check if the value of the given node is within range if not, we can discard that particular subtree and thereby reduce our search space

• increment the total variable at each recursive call

def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        total = 0
        if not root:
            return 0
        if root.val > low:
            total += self.rangeSumBST(root.left, low, high)
        if root.val < high:
            total += self.rangeSumBST(root.right, low, high)
        if root.val >= low and root.val <= high:
            total += root.val


        return total

Time and Space complexity

We are searching through the BST so time complexity is O(n) however, we will only itereate through the nodes which lie within the range. The space complexity is O(n) as we are making recursive calls which takes additional space to maintain the function call stack.

That was a tricky one. I plan on providing an in-depth post about BST to explore more about them. Until next post!