How do you solve Range Sum of BST on LeetCode?

Range Sum of BST (LeetCode #938) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Utilizing the properties of a BST can significantly reduce the number of nodes we need to check.

What is the brute force solution for Range Sum of BST?

The brute force approach for Range Sum of BST is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we traverse the entire tree and check each node's value to see if it falls within the specified range. If it does, we add it to our sum. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Range Sum of BST?

Range Sum of BST uses the following concepts: Tree, Depth-First Search, Binary Search Tree, Binary Tree. The recommended patterns to study are: Depth-First Search (DFS), Recursion, Binary Search Tree properties.

What are the interview tips for Range Sum of BST?

Always mention the properties of a BST when discussing traversal methods. Explain your thought process clearly; interviewers appreciate understanding your reasoning. Practice dry runs of your code with sample inputs to ensure you can trace your logic.

What are common mistakes when solving Range Sum of BST?

Not leveraging the BST properties, leading to unnecessary checks. Forgetting to handle edge cases, such as when the tree is empty.

#938

Range Sum of BST

Easy

TreeDepth-First SearchBinary Search TreeBinary TreeDepth-First Search (DFS)RecursionBinary Search Tree properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal solution leverages the properties of a binary search tree (BST) to skip unnecessary nodes. Instead of visiting every node, we can make decisions based on the current node's value, allowing us to reduce the number of nodes we need to check.

⚙️

Algorithm

5 steps

1Step 1: Start from the root of the BST.
2Step 2: If the current node's value is less than low, move to the right child (all values to the left are too small).
3Step 3: If the current node's value is greater than high, move to the left child (all values to the right are too large).
4Step 4: If the current node's value is within the range [low, high], add it to the sum and check both children.
5Step 5: Continue this process until all relevant nodes are checked.

solution.py16 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def rangeSumBST(root, low, high):
9    if not root:
10        return 0
11    if root.val < low:
12        return rangeSumBST(root.right, low, high)
13    elif root.val > high:
14        return rangeSumBST(root.left, low, high)
15    else:
16        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)

ℹ

Complexity note: The time complexity is O(n) in the worst case (when the tree is unbalanced), but on average, it can be O(log n) for balanced trees. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Utilizing the properties of a BST can significantly reduce the number of nodes we need to check.
2Recursive traversal can be optimized by avoiding unnecessary branches.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.