Problem statement

You are given the root of a binary search tree (every value in a node's left subtree is smaller than the node's value, every value in its right subtree is larger) and two integers low and high.

Return how many nodes hold a value in the inclusive range [low, high].

Example 1

Input: root = [10,5,50,1,null,40,100], low = 5, high = 45
Output: 3
Explanation: 5, 10 and 40 lie in [5, 45]; 1, 50 and 100 do not.

Example 2

Input: root = [5,4,6,3,null,null,7], low = 2, high = 8
Output: 5
Explanation: Every node lies in [2, 8].

Example 3

Input: root = [8,3,10], low = 4, high = 7
Output: 0
Explanation: No value lies between 4 and 7.

Constraints

• 1 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^5
• all node values are distinct
• root is a valid binary search tree
• 1 <= low <= high <= 10^5

Hints for Count BST Nodes That Lie in a Given Range

1. Hint 1

   Visiting every node and testing it works, but the ordering lets you skip whole subtrees.

2. Hint 2

   If a node's value is below low, nothing in its left subtree can be in range — and symmetrically above high.

3. Hint 3

   Count the node and descend both ways only when its value is inside the range; otherwise descend into the one side that can still hold in-range values.

How to solve Count BST Nodes That Lie in a Given Range

A node outside the range rules out one of its subtrees entirely, so the search only enters the parts of the tree that can still contain in-range values.

Approach

1. If the node is null, it contributes 0.
2. If its value is below low, return the count of its right subtree (the left one is smaller still).
3. If its value is above high, return the count of its left subtree.
4. Otherwise return 1 plus the counts of both subtrees.

Why it works

Every value in the left subtree of a node below low is smaller than that node and so below low too; skipping it loses nothing. The same holds for the right subtree of a node above high. Every node that is in range is reached, because its ancestors are either in range (both sides explored) or out of range on the side that keeps it.

Complexity

• Time — O(h + k), h the height and k the number of nodes in range
• Space — O(h) for the recursion

Pitfalls

• Both ends are inclusive: a node equal to low or high counts.
• Do not stop at a node outside the range — its other subtree can still hold in-range values.

Reference solution

Python

from typing import Optional

def getCount(root: Optional[TreeNode], low: int, high: int) -> int:
    if root is None:
        return 0
    if root.val < low:
        return getCount(root.right, low, high)
    if root.val > high:
        return getCount(root.left, low, high)
    return 1 + getCount(root.left, low, high) + getCount(root.right, low, high)

Java

public static int getCount(TreeNode root, int low, int high) {
    if (root == null) return 0;
    if (root.val < low) return getCount(root.right, low, high);
    if (root.val > high) return getCount(root.left, low, high);
    return 1 + getCount(root.left, low, high) + getCount(root.right, low, high);
}

C++

int getCount(TreeNode* root, int low, int high) {
    if (!root) return 0;
    if (root->val < low) return getCount(root->right, low, high);
    if (root->val > high) return getCount(root->left, low, high);
    return 1 + getCount(root->left, low, high) + getCount(root->right, low, high);
}

JavaScript

var getCount = function(root, low, high) {
    if (root === null) return 0;
    if (root.val < low) return getCount(root.right, low, high);
    if (root.val > high) return getCount(root.left, low, high);
    return 1 + getCount(root.left, low, high) + getCount(root.right, low, high);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy
• Nodes at Distance K from Root Easy