CareerCup

Interesting, this was one of the questions of my second interview. This was my answer:
- Suppose we know the size of the left subtree for each node.
- We want the number of values in the interval [A, B]. This is the same as the number of values up to B minus the number of values less than A.
- So we can reduce this question to finding the number of values up to X.
1) Start at the root
2a) If the value we search is less or equal to current node value. Then this node and all values to the right are larger or equal to this value and we can ignore them. Recurse on the left subtree
2b) The value we search is larger than the current node value. Then this node and all values in the left subtree are less than this value. Recurse on the right subtree.

On a balanced BST, this algorithm takes O(log N) time.

struct TreeNode {
	TreeNode * left, * right;
	int val, left_subtree_size;
};
int getLess(TreeNode* node, int v) {
	if (node == NULL)
		return 0;
	if (v <= node->val)
		return getLess( node->left , v);
	return 1 + node->left_subtree_size + getLess(node->right, v);
}
int Solve(TreeNode * root , int from, int to) {
	return getLess(root, to+1) - getLess(root, from);  // to+1 to get #values <= to
}

C++ code

{
struct node{
	struct node *left,*right;
	int lcount,rcount;
	int data;
}*root;
const int INFINITY=1000000000;
int low,high;
int main()
{
	int low,high;
	//build tree and input low and high...
	int res=findcount(root,-INFINITY,INFINITY);
	printf("result: %d\n",res);
	return 0;
}
int findcount(struct node * root,int lbound,int rbound)
{
	if(root==NULL)
		return 0;
	if(root->data > high)
	{
		//search left side only
		return findcount(root->left,lbound,root->data);
	}
	else if(root->data < low)
	{
		//search left side only
		return findcount(root->right,root->data,rbound);
	}
	else
	{
		//search both side
		if(lbound>=low && rbound<=right)//if all further children are within low & high, no need to iterate further 
			return 1 + root.lcount + root.rcount;
		else
			return 1 + findcount(root->left,lbound,root->data) + findcount(root->right,root->data,rbound);
	}
}

}

There can be 2 ways to get the number of nodes.

Approach 1:
With extra space:
Step1: While inserting elements in BST, keep count of left and right children at every node including root.
Step2: search(min, max) At the search time, total nodes between the min and max will be
left child count of root + right child count of root - left child count of min node - right child count of max nodes + 1 for root himself

Explanation:

For BST -- search(3,20)

10		
              /     \		
	    5      20
	  /   \      /   \		
	 3   7 15  25
        /   	      \	
      1 	      17

Search for min element in BST. Get the left and right child counts.
For 3: left count = 1 and right count = 0

Search for max element BST. Get the left and right child counts.
For 20: left count = 2 and right count = 1

Get the left and right child count of the root.
For root: left count = 4 and right count = 4

So the total number of elements between min and max would be
left child count of root + right child count of root - left child count of min node - right child count of max nodes + 1 for root himself

4 + 4 - 1 - 1 + 1 = 7 nodes

Time taken for finding nodes between min and max:
Search for min element: Worst case: O(N)
Search for max element: Worst Case O(N)
Calculation: O (1)

Total Time taken: O(N) + O(N) + O(1) = O(N)


Approach 2:
Second approach would be not to store any additional information at the node level.
Once the BST is built, perform in-order traversal of the BST and start counting the elements between min and max elements given in the BST.

Total Time taken :
For in order traversal O(N)
For counting elements: O(1)

Total time: O(N)

I will post the code for 2 approaches in short time.

Here's a simple solution in Python. Runs in O(n) time, which is asymptotically optimal.

def numNodesBetweenValues(root, lowVal, highVal):
    if root is None:
        return 0

    ret = 0
    if lowVal < root.val:
        ret += numNodesBetweenValues(root.left, lowVal, highVal)

    if lowVal <= root.val and highVal >= root.val:
        ret += 1

    if highVal > root.val:
        ret += numNodesBetweenValues(root.right, lowVal, highVal)

    return ret

//Count no of nodes between two keys in a bst
//These keys can present or not in bst
//do not include these keys even if they present there in counting

#include<iostream>
using namespace std;


struct Node
{
  int data;
  Node *left;
  Node *right;
  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {
   
  }
};

void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else
  {
      return;//Already present key
     
  }
}

//appproach here we will use is inorder
int CountNodesBetweenTwoKeys(Node* root, int key1, int key2)
{
   if(root == NULL) return 0;

   if(root->data == key1 || root->data == key2)
   return 0; //used to skip include keys node

   int n1 = 0;
   int n2 = 0;

   if(root->data > key1)//do not do this mistake if(root->left->data > key1)
   n1 = CountNodesBetweenTwoKeys(root->left,key1,key2);

   if(root->data < key2)//do not do this mistake if(root->right->data < key2)
   n2 = CountNodesBetweenTwoKeys(root->right,key1,key2);

   return n1+n2 + 1;//do not forget to add 1 that is used as counter
}


int main()
{
  
   
   Node *root2 = NULL;
   Insert(&root2,40);
   Insert(&root2,20);
   Insert(&root2,60);
   Insert(&root2,10);
   Insert(&root2,30);
   Insert(&root2,50);
   Insert(&root2,70);
   Insert(&root2,5);
   Insert(&root2,15);
   Insert(&root2,25);
   Insert(&root2,35);
   Insert(&root2,45);
   Insert(&root2,55);
   Insert(&root2,65);
   Insert(&root2,75);
   Insert(&root2,4);
   Insert(&root2,6);
   Insert(&root2,14);
   Insert(&root2,16);
   Insert(&root2,24);
   

   cout<<CountNodesBetweenTwoKeys(root2,3,75);
   return 0;
}

public int countNode (Tree node, int min, int max){

if(node == null){
return 0;
}
else if (node.data< min || node.data > max) {
return 0;
}

else {

if (node.data > min && node.data < max) {
return (1+ countNode(node.left,min,max) + countNode(node.right,min,max));

}
else {
return 0;
}


}
}

/*
	Assume there is a method 
	
	Node search(BST T, int number)
	
	which returns the node if found otherwise returns the leaf node where 
	it can be inserted as a left or right child

*/
int findNumberCountBetween(BST T, int small, int large)
{
	return getCountOfNodeLessThan(T, large)- getCountOfNodeLessThan(T, small);
	
}
pblic int getCountOfNodeLessThan(BST T, int number)
{
	count = 0;
	Node child = search(T,number);
	if (child.value() <= number)
	{
		count ++;
	}
	Node parent = child.getParent();
	while(parent.leftChild() != child)
	{
		conut ++ /* add 1 for including the parent*/
		count = count + parent.getNumberOfChildAtLeftSubTree();
		child = parent;
		parent.parent.getParent();
	}
	return count;
}

public int InBetweenRange(int i, int j, BinarySearchTree root)
        {
            if (i <= root.data && root.data <= j)
            {
                return 1 + InBetweenRange(i, j, root.leftchild) + InBetweenRange(i, j, root.rightchild);
            }
            else if (root.data < i)
            {
                return InBetweenRange(i, j, root.leftchild);
            }
            else 
            {
                return InBetweenRange(i, j, root.rightchild);
            }
        }

Assume i < j

private static int getCountBetweenRange(Node root, int min, int max){

if (root == null) {
return 0;
}

Queue<Node> helperQueue = new LinkedList<Node>();
helperQueue.add(root);

int count =0;

while(!helperQueue.isEmpty()){
Node temp = helperQueue.remove();

if(temp.data>= min && temp.data<=max){
count++;
}

if (temp.left != null) {
helperQueue.add(temp.left);
}

if (temp.right != null) {
helperQueue.add(temp.right);
}
}

return count;
}

private static int getCountBetweenRange(Node root, int min, int max){
		
		if (root == null) {
			return 0;
		}

		Queue<Node> helperQueue = new LinkedList<Node>();
		helperQueue.add(root);
		
		int count =0;
		
		while(!helperQueue.isEmpty()){
			Node temp = helperQueue.remove();
			
			if(temp.data>= min && temp.data<=max){
				count++;
			}
			
			if (temp.left != null) {
				helperQueue.add(temp.left);
			}

			if (temp.right != null) {
				helperQueue.add(temp.right);
			}
		}
		
		return count;
	}