Count BST subtrees that lie in given range - GeeksforGeeks
Given a Binary Search Tree (BST) of integer values and a range [low, high], return count of nodes where all the nodes under that node (or subtree rooted with that node) lie in the given range.
http://code.geeksforgeeks.org/dOyzNK ???
Read full article from Count BST subtrees that lie in given range - GeeksforGeeks
Given a Binary Search Tree (BST) of integer values and a range [low, high], return count of nodes where all the nodes under that node (or subtree rooted with that node) lie in the given range.
Input: 10 / \ 5 50 / / \ 1 40 100 Range: [5, 45] Output: 1 There is only 1 node whose subtree is in the given range. The node is 40
The idea is to traverse the given Binary Search Tree (BST) in bottom up manner. For every node, recur for its subtrees, if subtrees are in range and the nodes is also in range, then increment count and return true (to tell the parent about its status). Count is passed as a pointer so that it can be incremented across all function calls.
// A recursive function to get count of nodes whose subtree
// is in range from low to hgih. This function returns true
// if nodes in subtree rooted under 'root' are in range.
bool
getCountUtil(node *root,
int
low,
int
high,
int
*count)
{
// Base case
if
(root == NULL)
return
true
;
// call inRange first, so if false, no need to check its subtree
// Recur for left and right subtrees
bool
l = (root->left) ? getCountUtil(root->left, low, high, count) :
true
;
bool
r = (root->right) ? getCountUtil(root->right, low, high, count) :
true
;
// If both left and right subtrees are in range and current node
// is also in range, then increment count and return true
if
(l && r && inRange(root, low, high))
{
++*count;
return
true
;
}
return
false
;
}
// A wrapper over getCountUtil(). This function initializes count as 0
// and calls getCountUtil()
int
getCount(node *root,
int
low,
int
high)
{
int
count = 0;
getCountUtil(root, low, high, &count);
return
count;
}
bool
inRange(node *root,
int
low,
int
high)
{
return
root->data >= low && root->data <= high;
}
Read full article from Count BST subtrees that lie in given range - GeeksforGeeks