Log inSign up
mediumGeeksforGeeksNot Started

Count BST Nodes in a Given Range

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a Binary Search Tree (BST) and a range [low, high], count the number of nodes in the BST whose values fall strictly within the inclusive range [low, high].

You should leverage the BST properties to prune unnecessary subtrees and minimize node visits.

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.data <= 105
  • 1 <= low <= high <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply the BST invariant to prune branches outside the search interval.
  • Derive the O(K + H) time complexity for range queries.
  • Implement both recursive and iterative stack-based pruning traversals.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Range query on Binary Search Tree.
  • Count or sum nodes between [L, R].
  • Requirement to run faster than full O(N) tree traversal.

Algorithmic Decision Tree:

  • Compare root.val with low and high before recursing.
  • Prune left subtree when root.val < low.
  • Prune right subtree when root.val > high.

Connected Patterns:

Range Sum of BSTTrim a Binary Search TreeSearch in a Binary Search Tree

1. Full Tree Traversal (Unpruned)

Intuition

Visit every node in the tree using preorder or inorder traversal. For each visited node, test if low <= node.val <= high. If true, increment count. This takes O(N) time regardless of whether the range contains 0 nodes or all nodes.

When to apply: Baseline comparison for generic binary trees where BST properties do not hold.

Algorithm

  1. Traverse every node in the tree using standard DFS/BFS and count how many satisfy low <= node.val <= high without using BST properties.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int getCount(Node* root, int l, int h) {
13 if (!root) return 0;
14 int count = (root->data >= l && root->data <= h) ? 1 : 0;
15 return count + getCount(root->left, l, h) + getCount(root->right, l, h);
16 }
17};
18
19int main() {
20 Node* root = new Node(10);
21 root->left = new Node(5);
22 root->right = new Node(50);
23 root->left->left = new Node(1);
24 root->left->right = new Node(7);
25 root->right->left = new Node(40);
26 root->right->right = new Node(100);
27
28 Solution sol;
29 std::cout << "Count in [5, 15]: " << sol.getCount(root, 5, 15) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack

2. Iterative Stack Traversal with BST Pruning

Intuition

Maintain an explicit stack. Push the root. While the stack is non-empty, pop curr. If curr.data is within [l, h], increment count and push both left and right children. If curr.data < l, only push curr.right. If curr.data > h, only push curr.left.

When to apply: When avoiding recursion stack limits or operating in languages with strict recursion depth limits.

Algorithm

  1. Use an explicit stack and push only valid child branches using BST boundary comparisons.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4struct Node {
5 int data;
6 Node* left;
7 Node* right;
8 Node(int val) : data(val), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13 int getCount(Node* root, int l, int h) {
14 if (!root) return 0;
15 int count = 0;
16 std::stack<Node*> st;
17 st.push(root);
18
19 while (!st.empty()) {
20 Node* curr = st.top();
21 st.pop();
22
23 if (curr->data >= l && curr->data <= h) {
24 count++;
25 if (curr->left) st.push(curr->left);
26 if (curr->right) st.push(curr->right);
27 } else if (curr->data < l) {
28 if (curr->right) st.push(curr->right);
29 } else { // curr->data > h
30 if (curr->left) st.push(curr->left);
31 }
32 }
33 return count;
34 }
35};
36
37int main() {
38 Node* root = new Node(10);
39 root->left = new Node(5);
40 root->right = new Node(50);
41 root->left->left = new Node(1);
42 root->left->right = new Node(7);
43 root->right->left = new Node(40);
44 root->right->right = new Node(100);
45
46 Solution sol;
47 std::cout << "Count in [5, 15]: " << sol.getCount(root, 5, 15) << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(K + H) where K is nodes in range and H is tree height
  • Space complexity: O(H) explicit stack space

3. Recursive BST Pruning (Divide and Conquer)

Intuition

1. Base case: if (!root) return 0; 2. If root.data > h: all valid nodes must be strictly in the left subtree -> return getCount(root.left, l, h); 3. If root.data < l: all valid nodes must be strictly in the right subtree -> return getCount(root.right, l, h); 4. If l <= root.data <= h: count 1 for current node, plus recursive counts from both left and right children -> return 1 + getCount(root.left, l, h) + getCount(root.right, l, h);

When to apply: Standard production solution for BST range queries.

Algorithm

  1. Recursively prune subtrees outside the interval using clean divide-and-conquer branching rules.

BST Range Pruning Traversal Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Count increments by 1
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
root = 10: 5 <= 10 <= 15 -> Valid!
Decision / next transition
1
Why this step matters

Count increments by 1. Recurse into left child (5) and right child (50).

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int getCount(Node* root, int l, int h) {
13 if (!root) return 0;
14
15 // If current node is greater than high, only left subtree can have valid nodes
16 if (root->data > h) {
17 return getCount(root->left, l, h);
18 }
19
20 // If current node is smaller than low, only right subtree can have valid nodes
21 if (root->data < l) {
22 return getCount(root->right, l, h);
23 }
24
25 // Current node is within [l, h]
26 return 1 + getCount(root->left, l, h) + getCount(root->right, l, h);
27 }
28};
29
30int main() {
31 Node* root = new Node(10);
32 root->left = new Node(5);
33 root->right = new Node(50);
34 root->left->left = new Node(1);
35 root->left->right = new Node(7);
36 root->right->left = new Node(40);
37 root->right->right = new Node(100);
38
39 Solution sol;
40 std::cout << "Count in [5, 15]: " << sol.getCount(root, 5, 15) << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(K + H) where K is number of matching nodes and H is tree height
  • Space complexity: O(H) recursion stack space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Tree Traversal (Unpruned)O(N)O(H) recursion stackTraverse every node in the tree using standard DFS/BFS and count how many satisfy low <= node.val <= high without using BST properties.O(N)
2.Iterative Stack Traversal with BST PruningO(K + H) where K is nodes in range and H is tree heightO(H) explicit stack spaceUse an explicit stack and push only valid child branches using BST boundary comparisons.O(K + H) where K is nodes in range and H is tree height
3.Recursive BST Pruning (Divide and Conquer)OptimalO(K + H) where K is number of matching nodes and H is tree heightO(H) recursion stack spaceRecursively prune subtrees outside the interval using clean divide-and-conquer branching rules.O(K + H) where K is number of matching nodes and H is tree height

Common Pitfalls & Crucial Edge Cases

Reversing the pruning inequalities

Writing if (root.data > h) return getCount(root.right) visits the completely wrong subtree.

Using `<` and `>` instead of `<=` and `>=`

Excludes boundary values that are equal to low or high.

Assuming tree is a general binary tree

Visiting both children unconditionally throws away the O(K + H) BST advantage.

Crucial Edge Cases to Validate:

  • Range completely outside the BST (`[200, 300]` on tree with max 100) — Prunes quickly down one path and returns 0.
  • Range covers the entire tree (`[-10^5, 10^5]`) — Visits all nodes and returns total size N.
  • Single node tree within range — Returns 1.
  • Single node tree outside range — Returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the pruning conditions aloud: 'If root.val > high, right subtree is guaranteed to be out of range, so I only explore left.'
  2. Mention the complexity is O(K + H) rather than simply O(N), showing depth of analysis.
  3. Compare with 'Range Sum of BST' (which is identical in logic, replacing + 1 with + root.val).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When root.data > high, which subtree should be explored?

2.What is the worst-case time complexity of the optimal pruning approach when the range [low, high] matches no elements and lies entirely above the maximum key in a balanced BST?

3.Does the order of recursive calls (inorder vs preorder) affect the final count returned by the pruning algorithm?

Back to DSA Sheet