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.
Given the root node
root of a binary search tree and two integers
high, return the sum of values of all nodes with a value between
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.
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
- Begin at the root of the BST.
- If the value of the root is within the range
[low, high], add it to the sum.
- If the value of the root is greater than
low, traverse the left subtree.
- If the value of the root is less than
high, traverse the right subtree.
- 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
- 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)
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.