Given a BST, count subtrees in it whose nodes lies within a given range.

For example, consider below BST. The number of subtrees with nodes in the range [5, 20] are 6.

The subtrees are:

6 9 8 10 12 18

/ \ / \

6 9 8 12

/ \

6 9

Simple solution is to traverse the tree and for each encountered node, check if all nodes under subtree rooted under the node are within the given range or not. The time complexity of above solution is O(n^{2}). We can improve time complexity to linear by traversing the tree in bottom-up manner and transfer some information from children to the parent node.

The idea is to perform post-order traversal on the given BST. Then for any node, if both its left and right subtree are within the range along with the node itself, we can say that the subtree rooted with this node is also within the range. This algorithm can be implemented as follows in C++ where we’re maintaining a reference variable to store the subtrees count –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <iostream> using namespace std; // Data structure for BST node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Recursive function to insert an key into BST Node* insert(Node* root, int key) { // if the root is null, create a new node an return it if (root == nullptr) return new Node(key); // if given key is less than the root node, recurse for left subtree if (key < root->data) root->left = insert(root->left, key); // else recurse for right subtree else root->right = insert(root->right, key); // return root node return root; } // Function to count subtrees in a BST whose nodes lies within a given range // It returns true if whole subtree rooted at given node is within range bool findSubTrees(Node* root, int low, int high, int& count) { // base case if (root == nullptr) return true; // increment the subtree count by 1 and return true if the root node, // left and right subtree are within the range if (findSubTrees(root->left, low, high, count) && findSubTrees(root->right, low, high, count) && (root->data >= low && root->data <= high)) { count++; return true; } return false; } int main() { // input range int low = 5, high = 20; // BST keys to construct BST shown in the diagram int keys[] = { 15, 25, 20, 22, 30, 18, 10, 8, 9, 12, 6 }; // construct BST Node* root = nullptr; for (int key : keys) root = insert(root, key); // get subtrees count int count = 0; findSubTrees(root, low, high, count); cout << "The number of subtrees are: " << count; return 0; } |

`Output:`

The number of subtrees are: 6

The time complexity of above solution is O(n) and auxiliary space used by the program is O(h) for recursion call stack where h is the height of the BST.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply