CareerCup

Easy since the input tree is BST. if we do inorder traversal we will get data in sorted order.
1. Do inorder traversal
2. Have 2 class member variable prevValue and valueCount
3. while traversing check if node.data == prevValue the increase the count
4. else print the value and count - 1

All set
///
public void printExtraDups(Node root){
//int prev = 0;
if(root != null)
{

if (root.left != null )
printExtraDups(root.left);

if( prevData == root.data) count++;
else System.out.println("Prev: "+prevData+" count: "+(count -1));

prevData = root.data;

if(root.right !=null )
printExtraDups(root.right);
}
}
\\\

Use a regular BST search but send parent value to children and keep a class level HashMap of current dups
{
HashMap<BSTNode, Integer> dupMap = HashMap<BSTNode, Integer>();

//head will trying to compare with null
void findDups(BSTNode parent, BSTNode current)
{
if(current.data == parent.data)
{
//see if already in map, if not put it in with value 1, else pull out value, increment, insert again
}
parent = current
for(BSTNode child : current.getChildren)
{
findDup(child, parent)
}
}

}



Not the best pseudo code but you get the point

just use inorder tree traversal once and then traverse the array to find number of duplicates.

I just wonder is input2 tree a binary tree?

Could you please confirm that tree is Binary tree or BST ? If its BST then what is the duplicity rule in BST I mean "left-key <= root-key < right-key" or "left-key <= root-key <= right-key" or "left-key < root-key <= right-key" ??

import java.util.ArrayList;

public class amazon
{
private static node root=new node();

void input(int value)
{
node temp=new node();
temp.value=value;
if(root==null)
{
root=temp;
}
else
{
setvalues(root, temp);
}

}


void setvalues(node root, node temp)
{
if(root.value>temp.value)
{
if(root.left==null)
{
root.left=temp;
}
else
setvalues(root.left, temp);
}

if(root.value<=temp.value)
{
if(root.right==null)
{
root.right=temp;
}
else
setvalues(root.right, temp);
}

}

static void printDuplicates(ArrayList<Integer> tem1)
{
int pointer1=tem1.get(0), pointer2=0;
for(int x=1;x<tem1.size();x++)
{
if(pointer1==tem1.get(x))
{
pointer2++;
}
else
{
System.out.println(pointer1+"hekllo"+pointer2);
pointer1=tem1.get(x);
pointer2=0;
}

}
}

public static ArrayList<Integer> display(node temp,ArrayList<Integer> tem1)
{
if(temp!=null)
{
display(temp.left, tem1);
tem1.add(temp.value);
System.out.println(temp.value);
display(temp.right, tem1);

}
return tem1;
}
}


class node
{
int value;
node left;
node right;
node()
{
this.value=0;
this.left=null;
this.right=null;
}
}

Do inorder traversal and put each element in an array. Now traverse the array and have 2 vars.
count and lookingFor. Initialize count=1 and lookingFor=a[0] if a is the obtained array.
Now,
int i=1;
while(i<length)//length is array length
{
if(a[i]==a[i-1])
count++;
else
{
cout<<lookingFor<<"is duplicated"<<count<<"times\n";
lookingFor = a[i+1];
count=1;
i++;
}
}

In the input 2 how can node 3 be on both side of root node 3??? Either it should be on left side or right side. If this is not the case then inorder traversals would fail and won't give result in a sorted manner. Hashing is the only solution in that case.

As I feel, given example in question is not a BST.
@sastry.soft: we can't keep BST according to definition. but if we don't have choice and we have to keep duplicates then either we should keep it as left child or right child but not both.

Is the given tree a Binary Search tree?

import java.util.*;


class Node{
int value;
Node left=null;
Node right=null;
public Node(int value){
this.value=value;
}
public int get(){

return this.value;
}

public void set(int value){

this.value=value;
}

}
class hashmapResult{
HashMap hm = new HashMap();
}

public class BST {

/**
* @param args
*/



public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Starting...");
System.out.println();

int bstHeight=5;
double totalnumofNode=Math.pow(2, bstHeight)-1;
LinkedList<Node> bst= new LinkedList<Node>();

constructBst(bst,bstHeight,totalnumofNode);

for(int i=0;i<totalnumofNode;i++)
{
if(bst.get(i).left==null||bst.get(i).right==null){
System.out.println("Node " +i +": "+bst.get(i).value+" Left: NULL Right: NULL");
}
else{
System.out.println("Node " +i +": "+bst.get(i).value+" Left: "+bst.get(i).left.value+" Right: "+bst.get(i).right.value);

}

}

printDups(bst);


}

private static void printDups(LinkedList<Node> bst){
hashmapResult hmR= new hashmapResult();
fillHashmap(bst.getFirst(),hmR);
Set entries = hmR.hm.entrySet();
Iterator it = entries.iterator();
while(it.hasNext()) {
Map.Entry me = (Map.Entry)it.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();

}

private static void fillHashmap(Node root,hashmapResult hmR){
if(root!=null&&root.value!=0){

if(root.left!=null&&root.left.value!=0)
{
fillHashmap(root.left, hmR);
}

Set keys = hmR.hm.keySet();
if(!keys.contains(root.value))
{
hmR.hm.put(root.value,0);
}
else
{
int count=(int)hmR.hm.get(root.value)+1;
hmR.hm.put(root.value,count);
}

if(root.right!=null&&root.right.value!=0)
{
fillHashmap(root.right, hmR);
}

}
}


private static void constructBst(LinkedList<Node> bst, int bstHeight,double totalnumofNode) {
// TODO Auto-generated method stub
Random randomGenerator = new Random();

for(int i=0;i<totalnumofNode;i++){
Node node=new Node(0);
bst.add(node);
}

for(int i=0;i<Math.pow(2, bstHeight-1)-1;i++){
bst.get(i).left=bst.get(i*2+1);
bst.get(i).right=bst.get(i*2+2);
}

for(int i=0;i<10;i++){
int randomInt = randomGenerator.nextInt(5)+1;
insertNode(bst.get(0),randomInt);
}

}

private static void insertNode(Node root,int value){
if(root.value==0)
{
root.value=value;
}
else{
if(root.value>value)
insertNode(root.left,value);
if(root.value<=value)
insertNode(root.right,value);
}
}


}

The given tree in input 2 is NOT a BST. A BST must maintain an invariant that given any node, all nodes in the sub-tree rooted at the given node must follow some kind of order, say all nodes in the left side of the root of the sub-tree must be less than the root (given node) and similarly all nodes from right side of the sub-tree must be greater than the root (given node). For a BT to become a BST this invariant must be true for all sub-trees rooted at all of its nodes. The tree in example 2 doesn’t follow this invariant as it has root 3 which has node 5 on its left. I think ‘pradegup’ has already noticed this anomaly – kudos to him.

However the question can still be valid for either a BT or a BST. In both cases a traversal of tree along with comparing duplicate check and maintaining their count can be done in theta(n) time. In case of BT I think additional memory in the form of hash-table like data structure would be required in maintaining the duplicate key’s count. However for BST we don’t need any additional memory if we maintain a collection of values for duplicate keys ensuring even a duplicate key occurs only once in the tree (but they may have more than one value per duplicate key). Anyway the idea is that with actual implementation of a BST with duplicates the need for additional memory (Hash-table) may go away whereas for BT additional memory is essential.

int prev = -1;
int count = 0;

print_dup (node *root)
{
    if (root != NULL)
    {
        print_dup(root->left);
        if (root->val == prev)
            count++;
        else
        {
            if (count > 0)
            {
                   printf (" num:%d, count:%d", prev, count);
                   count = 0;
             }
        }
        print_dup(root->right);
    }
}

void print_extra_duplicates(node *root)
{
int count = 0;
node *tmp;

if(root == NULL) return;

print_extra_duplicates(root->left);

tmp = root->right;
while(tmp != NULL && root->data == tmp->data)
{
count++;
tmp = tmp->right;
}


if(count)
{
printf("\n Data:%d Extra Duplicate:%d\n", root->data, count);
root = tmp;
if(root == NULL) return ;
}

print_extra_duplicates(root->right);
}

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
node *left;
int data;
node *right;
};

int inorder_array[20];
int index;
node *insert(node *root, int data);
void print_extra_duplicates(node *root);
void inorder_traverse(node *);

int main()
{
printf("\n Welcome Pankaj....\n");
node *root = NULL;
int n1 =0, sum = 0;
int n,i;
int input[20];
printf("\n Enter size of array=");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&input[i]);

for(i=0;i<n;i++)
{
root = insert(root, input[i]);
}

inorder_traverse(root);
print_extra_duplicates(root);

return 0;
}

void inorder_traverse(node *root)
{
if(root == NULL) return;

inorder_traverse(root->left);

inorder_array[index++] = root->data;

inorder_traverse(root->right);
}

void print_extra_duplicates(node *root)
{
int count = 0, i;
node *tmp;

for(i = 0; i<index-1; i++)
{
while(inorder_array[i] == inorder_array[i+1])
{
i++;
count++;
}
if(count)
{
printf("\n Data:%d Extra Duplicate:%d\n", inorder_array[i], count);
}
count =0;
}
}

node *insert(node *root, int data)
{
if(root == NULL)
{
root = (node *)malloc(sizeof(node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}

if(root->data > data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);

return root;
}

int countDuplicates(Node node, int value){
if(node == null) return 0;
return countDuplicates(node.left, value) +
countDuplicates(node.right, node.data) +
node.data==value?1:0
}

Call: countDuplicates(root, -1); // Assuming -1 is not presesnt in the tree

int countDuplicates(bnode node, int &prev)
{    
    if ( node == NULL) return 0;
    int lcount = countDuplicates(node->left, prev);
    prev = node->data;              
    int rcount = countDuplicates(node->right, prev); 
    return (prev == node->data)? lcount+rcount+1 : lcount+rcount;            
}

Are you sure if its a BST..because the examples you have given are not BST..

Keeping totalCount as global variable

private static Node fn2(Node root, Node prev) {
        if (root == null) return prev;
        prev = fn2(root.left, prev);
        if (prev!=null&&prev.data == root.data) {
            totalCount++;
        } else if(totalCount >0)
        {
            System.out.println("Node " + prev.data + " totalCount" + totalCount);
            totalCount = 0;
        }
        fn2(root.right, root);
        return root;

    }

Simply use iterative in-order traversal :

void extra_duplicates(Node root){
	Stack<Node> S = new Stack<Node>();
	Node current = root;
	int prev = -1;
	int dups = 0;
	do{
		while (current.leftChild != null){
			S.push(current);
			current = current.leftChild;
		}
		current = S.pop();
		if (current.val == prev){
			dups++;
		}else if {
			if (dups >0)
				System.out.prinln(curren.val + " : " + dups);
			dups++;
			prev = current.val;
		}
		if (current.rightChild != null)
			current = current.rightChild;
	}while (!S.isEmpty());
	return;
}

Can we have duplicates in BST?