CareerCup

It can be easily done using recursion.

void countInsideRange(node *root, int min, int max, int* count)
{
   if (root == NULL)
      return;
      
   countInsideRange(root->left, min, max, count);
   countInsideRange(root->right, min, max, count);
 
   if((root->key > min) && (root->key < max))
                 *count = *count + 1;
   
   return;
}

The answer will be in integer count value.

Following is one of the many ways to do this.

Take the inorder traversal. Since it is sorted you easily check the number of nodes having values between a and b.
O(n) where n is total number of nodes.

You can optimize the above if you count the node during traversal itself and reject the left child of nodes having values less than a and right child of nodes having values greater than b.

First find LCA of the Nodes.
return(LCA to Node1 distance + LCA to Node2 distance -1 )

Have a visitor which returns an int. If the current value is smaller than 'a', return the result of going right; if it's larger than 'b', return the result of going left.
If it's between the two, then go both ways and return the result of both added up plus one.

/**
* count the no of nodes in the  subtree rooted at root and containing n1 and n2.
*
*/
int countNodes(struct node* root)
{
int count=0;
    if(!root)
	      return count;
	else
	{
	      count=countNode(root->left);
		  count=countNode(root->right);
		  count++;
	}
	
	return count;
}




int LCA(struct node* root, int n1, int n2)
{
  if(root == NULL || root->data == n1 || root->data == n2)
    return -1; 
   
  if((root->right != NULL) && 
    (root->right->data == n1 || root->right->data == n2))
    return root->data;
  if((root->left != NULL) && 
    (root->left->data == n1 || root->left->data == n2))
    return root->data;    
     
  if(root->data > n1 && root->data < n2)
    return countNodes(root->data);
  if(root->data > n1 && root->data > n2)
    return LCA(root->left, n1, n2);
  if(root->data < n1 && root->data < n2)
    return LCA(root->right, n1, n2);

}

void GetCount(struct Node *node,int a,int b,int &count)
{
if(!node || node->data<a || node->data>b)
return;
GetCount(node->left,a,b,count);
if(node->data>a && node->data<b)
count++;
GetCount(node->right,a,b,count);
}

Why not first find the lesser one of a and b, and then traverse in-order traversal and stop when greater one is found?

int count(int a, int b, BST t)
{
if (!t) { return 0; }
else if (t->key < i) {
return count (i, j, t->right);
}

else if (t->key > j) {
return count(i, j, t->left);
}

else {
return (1 + count(i, j, t->left) + count(i, j, t->right));
}
}

public static int countNodesInRange(Integer a, Integer b, TreeNode<Integer> root) {

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

        if(root.value > a && root.value < b) {
            return 1 + countNodesInRange(a, b, root.left) + countNodesInRange(a, b, root.right);
        } else if(root.value >= b) {
            return countNodesInRange(a, b, root.left);
        } else if(root.value <= a) {
            return countNodesInRange(a, b, root.right);
        } else {
            return 0;
        }
    }

public static int countNodesInRange(Integer a, Integer b, TreeNode<Integer> root) {

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

        if(root.value > a && root.value < b) {
            return 1 + countNodesInRange(a, b, root.left) + countNodesInRange(a, b, root.right);
        } else if(root.value >= b) {
            return countNodesInRange(a, b, root.left);
        } else if(root.value <= a) {
            return countNodesInRange(a, b, root.right);
        } else {
            return 0;
        }
    }

This is to find least Common ancestor(LCA problem).

LCA