Binary Search TreesProblem 16 of 22
Count BST nodes that lie in a given range
Problem Statement
Given a BST and a range [low, high], count the number of nodes whose values lie within this range (inclusive).
Example:
10
/ \
5 50
/ \ / \
1 6 40 100
Range: [5, 45]
Output: 4 (nodes 5, 6, 10, 40 are in range)
Range: [1, 10]
Output: 4 (nodes 1, 5, 6, 10 are in range)
Approach 1: Brute Force (Complete Traversal)
Intuition
Traverse the entire tree and count nodes whose values fall within the given range.
Algorithm
- Traverse all nodes (any traversal works)
- For each node, check if value is within [low, high]
- Increment count if within range
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int countInRangeBruteForce(TreeNode root, int low, int high) {
if (root == null) return 0;
int count = (root.val >= low && root.val <= high) ? 1 : 0;
count += countInRangeBruteForce(root.left, low, high);
count += countInRangeBruteForce(root.right, low, high);
return count;
}
}Complexity Analysis
- Time Complexity: O(n) - Visit all nodes
- Space Complexity: O(n) - Recursion stack for skewed tree
Approach 2: Optimal (Using BST Property)
Intuition
Use BST property to prune search:
- If current value < low, all left subtree values are also < low (skip left)
- If current value > high, all right subtree values are also > high (skip right)
Algorithm
- If node value < low, only search right subtree
- If node value > high, only search left subtree
- If node value in range, count it and search both subtrees
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int countInRange(TreeNode root, int low, int high) {
if (root == null) return 0;
// If current node is less than low, skip left subtree
if (root.val < low) {
return countInRange(root.right, low, high);
}
// If current node is greater than high, skip right subtree
if (root.val > high) {
return countInRange(root.left, low, high);
}
// Current node is in range, count it and explore both subtrees
return 1 + countInRange(root.left, low, high) +
countInRange(root.right, low, high);
}
}Complexity Analysis
- Time Complexity: O(h + k) where k is number of nodes in range
- Space Complexity: O(h) - Recursion stack
Approach 3: Iterative (Using Stack)
Intuition
Use iterative traversal with explicit stack, applying the same pruning logic.
Algorithm
- Use stack to simulate recursion
- Apply BST property to decide which children to explore
- Count nodes in range
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int countInRangeIterative(TreeNode root, int low, int high) {
if (root == null) return 0;
int count = 0;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
if (node.val >= low && node.val <= high) {
count++;
// Both subtrees might have nodes in range
stack.push(node.left);
stack.push(node.right);
} else if (node.val < low) {
// Only right subtree might have nodes in range
stack.push(node.right);
} else {
// Only left subtree might have nodes in range
stack.push(node.left);
}
}
return count;
}
}Complexity Analysis
- Time Complexity: O(h + k) where k is nodes in range
- Space Complexity: O(h) - Stack space
Approach 4: Return Sum Instead of Count (Variant)
Intuition
Sometimes the problem asks for sum of values in range instead of count. Same approach works.
Algorithm
Same as count, but add values instead of incrementing count.
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int sumInRange(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.val < low) {
return sumInRange(root.right, low, high);
}
if (root.val > high) {
return sumInRange(root.left, low, high);
}
return root.val + sumInRange(root.left, low, high) +
sumInRange(root.right, low, high);
}
}Complexity Analysis
- Time Complexity: O(h + k)
- Space Complexity: O(h)
Key Takeaways
- BST Pruning: Key optimization - skip entire subtrees that can't contain valid nodes
- Three cases: node < low (go right), node > high (go left), node in range (check both)
- Related problem: LeetCode #938 - Range Sum of BST
- Time complexity: O(h + k) is optimal - must visit all k nodes in range
- Works for both count and sum variants
- Can be extended to find all nodes in range (return list instead of count)
- BST property makes range queries efficient compared to regular binary tree