CareerCup

Just do Inorder Traversal and count the Duplicates as Inorder will give you sorted order so you just need to compare currentValue with last value.

int count_dup(node *root, int &count)//initially count = 0
{
    static int prev = INT_MIN;
    if(root)
    {
       count_dup(root->left,&count);
       if(root->info == prev)
       ++*count;
       prev = root->info;
       count_dup(root->right,&count);
    } 
   return count;
}

Here is a snippet that solves this recursively. You could also pass the count as a by ref param.

private int TraverseDuplicateEx(HashSet<T> found, BSTNode node)
        {
            if (null == node)
                return 0;
            int count = 1;

            if (!found.Contains(node.Data))
            {
                found.Add(node.Data);
                count = 0;
            }

            count += TraverseDuplicateEx(found, node.Left);
            count += TraverseDuplicateEx(found, node.Right);
            return count;
        }

How are duplicates inserted? In the right subtree (based on example)?

Do a BFS traversal (only add pointers to nodes in the queue) and instead of removing elements from the front of the queue, just move the current pointer to the next element in the queue. For each new element added, compare it to the all the node from the current position of the queue back to the zero'th position. If there's a match, add 1 to count.

Search each and every element's duplicate on its path to root only. If it is a BST, then duplicate should be present on the root path only. Then, complexity should be O(n log n).

Since it is not mentioned, I assume that , you can destroy tree structure. What you need is do a rotation (right or left ) at each node and get a sorted linked list and do a linear walk on sorted list to get count of duplicates

O(n) Solution?????

Code in Java.

Things to note:

A duplicate for a node can occur only in right subtree so whenever rightSubTree is traverse update pass node's data as rootData.

private static void removeDuplicates(TreeEntry node,int rootData,int count) {
		
		if (node  == null)
			return ;
		
		if (node.data == rootData) {
			count++;
			System.out.println("Extra element is "+ rootData + " and count is " +count);
		}
		
		removeDuplicates(node.left,rootData,0);
		removeDuplicates(node.right,node.data,count);
	}

private int dupCounter;
    private Integer prevNode = null;

    private void countDupsInorder(Tree t)
    {
        if (t == null)
            return;

        countDupsInorder(t.left);

        if (prevNode == null)
            prevNode = t.value;
        else
            if (t.value == prevNode)
                dupCounter++;
            else
                prevNode = t.value;

        countDupsInorder(t.right);
    }

int previous=0;
inorder_tracversal(node* ptr)
{   if(ptr==null)
          return 0;
   
         inorder_traversal(ptr->left);
         if(previous==ptr->data)count++;previous=ptr->data;
         inorder_traversal(ptr->right);
       
}

1)do inorder traversal
2) campare adjacent no
if same don't do anything
else count++
3) return count

find inorder successor for each node...

1.) If we have link to the parent is really easy --> just iterate through the successors and check if curr node is duplicate to its successor. We will need O(1) space and O(n) time.
2.) The harder case is when there is no link to the parent node. This can be solved by recursion or using stack for traversing the inOrder of the tree. Both of them are O(n) time and O(logn) space. An example Java code for the recursion is bellow:

public int getDuplCount(TreeNode t, TreeNode prev) {
  int count = 0;
 
  if (t != null) {
   count += getDuplCount(t.left, prev);
 
   if (prev != null && t.data == prev.data)
    count++;
  
  //This will be needed if and Equal node goes on the left. In the example it goes on the right  so it is commented here
  //if (t.left != null && t.data == t.left.data)
    //count++;
   
   count += getDuplCount(t.right, t);
  }
 
  return count;
 }

When performing inorder traversal, duplicate keys will be visited together.

With space o(1) and complexity o(n)

void CountDuplicates(TNode *node, int *k)
{

  if (node== NULL) 
		return;
  
  CountDuplicates( node->left, k);
  
  if ( node->right != 0 )
  {
	if ( ( findtheMinValueofBST(node->right) == node->value) || node->value == node->right->value )
	(*k)=(*k)+1;
  }
  
  CountDuplicates(node->right,k);
}
  
int findtheMinValueofBST(TNode *node)
{
	if (node == NULL) return -1;

	while (node->left != NULL)
		node = node->left;
	return node->value;
}