435. Count BST Nodes in a Given Range

Given a binary search tree and two integers low and high, count how many nodes have a value between low and high, inclusive, and print that count. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). low and high are given on the next line.

Input: First line contains space-separated level-order tokens describing the BST ('N' marks an absent child). Second line contains the two integers low and high. Output: Print a single integer - the count of nodes whose value lies within [low, high].

1 <= number of nodes <= 10^5

The range is explicitly INCLUSIVE on both ends - a node exactly equal to low or high still counts, an easy boundary condition to get wrong if rushed.

Count how many nodes in a binary search tree have a value between a low and high bound, inclusive. Brute force: Visit every single node in the tree and check if it falls within range - this costs O(n) regardless of the BST structure, missing the opportunity to skip entire out-of-range subtrees. Optimised: Pruning an ENTIRE subtree the moment you know it's fully out of range (based on a single comparison at its root) can save large amounts of work on a well-balanced tree - in the best cases this runs much faster than a full traversal, though a worst-case tree where every node is in range still visits everything.

Traverse the tree recursively, but instead of storing values, increment a running counter directly whenever a visited node's value falls within [low, high]. This still visits every node exactly like the brute-force version, but it drops the O(n) auxiliary array entirely, needing only recursion-stack space proportional to the tree's height. Time: O(n) Space: O(h)

Traverse the entire tree in any order, appending every node's value into an auxiliary array regardless of the binary search tree structure, then scan that array afterward and count how many values fall within [low, high]. This is correct for any binary tree, not just a BST, but it wastes memory materializing every value up front and ignores the ordering information a BST already provides. Time: O(n) Space: O(n)

Exploit the BST ordering while recursing: if the current node's value is less than low, skip its entire left subtree since every value there is even smaller; if it's greater than high, skip the entire right subtree since every value there is even larger; otherwise count the node and recurse into both children. This can skip large swaths of the tree entirely whenever the query range is narrow relative to the tree's value spread, so although the worst case (a range covering the whole tree) still touches every node, typical and best-case behavior is much faster than the unconditional full traversal. Time: O(h + k) in typical cases, O(n) worst case Space: O(h)

1. At each node, check if its value falls within [low, high] - if so, count it. 2. If the node's value is LESS than low, its entire left subtree is also too small - skip exploring it entirely. 3. If the node's value is GREATER than high, its entire right subtree is also too big - skip exploring it entirely. 4. Otherwise, recurse into both children, since either side might still contain values in range.

Time: O(h + k) in favorable cases (h for reaching the range, k for the number of nodes actually in range), degrading to O(n) if the whole tree happens to be within range. Space: O(h) for the recursion stack.

Test with a range containing no nodes (answer 0), a range spanning every node, a node value exactly equal to low or high (still counted, inclusive), and a tree with 10^5 nodes for performance.

Be ready to explain clearly WHY pruning is safe here (a BST guarantees everything in a skipped subtree is uniformly too small or too big) - this pruning logic wouldn't be valid on a general, non-BST binary tree.