Leetcode – Range Sum of BST Solution in Python

Spread the love

Leetcode is a go-to platform for many coders and software engineers, offering a multitude of challenges that test one’s algorithmic prowess. One such interesting problem that verifies a candidate’s understanding of binary search trees (BST) is the “Range Sum of BST” problem. This article is designed to delve into the intricacies of the problem, simplify the approach, and provide a Python-based solution.

Problem Statement

Given the root node root of a binary search tree and two integers low and high, return the sum of values of all nodes with a value between low and high (inclusive).

The BST is guaranteed to have unique values.

Understanding the Problem

In essence, the problem is about traversing a BST and collecting values that fall within a specified range. While BST traversal is a standard operation, the challenge lies in optimizing the traversal to only process relevant nodes, leveraging the properties of the BST.

Key Insight

The nature of a BST is such that for any node:

  • All nodes to the left have values less than the node.
  • All nodes to the right have values greater than the node.

This property can be used to optimize the traversal, skipping entire subtrees that don’t fall within the [low, high] range.

Algorithm to Solve the Problem

  1. Begin at the root of the BST.
  2. If the value of the root is within the range [low, high], add it to the sum.
  3. If the value of the root is greater than low, traverse the left subtree.
  4. If the value of the root is less than high, traverse the right subtree.
  5. Return the computed sum.

Python Code Solution

A recursive solution works naturally for this problem given the recursive structure of BSTs:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0

        # Initialize sum to 0
        sum_val = 0

        # If current node's value is within range, add it to sum
        if low <= root.val <= high:
            sum_val += root.val
        
        # If current node's value is greater than low, then explore left subtree
        if root.val > low:
            sum_val += self.rangeSumBST(root.left, low, high)
        
        # If current node's value is less than high, then explore right subtree
        if root.val < high:
            sum_val += self.rangeSumBST(root.right, low, high)
        
        return sum_val

Complexity Analysis

  • Time Complexity: The worst-case scenario is O(N), where N is the number of nodes in the BST. However, on average, given a balanced BST, and due to skipping, the complexity would be closer to O(log N).
  • Space Complexity: The space is determined by the depth of the recursion stack. In the worst case, it’s O(N), but on average for a balanced BST, it’s O(log N).

Testing the Solution

To ensure the solution is correct:

# Create a simple BST:   10
#                       /  \
#                      5   15
#                     / \    \
#                    3   7    18

root = TreeNode(10)
root.left = TreeNode(5, TreeNode(3), TreeNode(7))
root.right = TreeNode(15, None, TreeNode(18))

# Test the solution
s = Solution()
print(s.rangeSumBST(root, 7, 15))  # Expected output: 32 (7 + 10 + 15)

Conclusion

The “Range Sum of BST” problem beautifully integrates the fundamental knowledge of binary search trees and efficient traversal strategies. The key is to recognize the inherent properties of BSTs and utilize them to prune out unnecessary traversals. This not only saves computational time but also makes the algorithm elegant. As always, understanding the problem deeply and visualizing the tree structure will aid in crafting an optimized solution.

Leave a Reply