## Interview Question

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 6 vote

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.

Comment hidden because of low score. Click to expand.
0

comparing current node to the last node will only count immediate duplicates i.e. in the example above, the duplicate of 3 and 5 will not be added

Comment hidden because of low score. Click to expand.
0

@amitmsingh Inorder traversal of that tree would be 2,3,3,4,5,5,8,8,8,10,10. Tell me if you cant calculate no of duplicates with this.

Comment hidden because of low score. Click to expand.
0

No need for extra hash or extra space, just inorder traversal and keeping the count does gives the result. Just need a bit of trick to print the node in the end rather than immediately.

``````void count_dups_bst(struct BstNode* root, int& count)
{
static struct BstNode* prev = NULL;
if(root)
{
count_dups_bst(root->left, count);
if(!prev && prev->data == root->data)
{
count++;
}
else
{
// just check if count > 0  & print that count with prev node
// this ensures that all occurences/count are taken care and the node is printed at the end.
if(count > 0)
cout << prev->data << "extra " << count << " times " << endl;

count = 0; // reset the count
}
prev = root;

count_dups_bst(root->right , count);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

If using a queue to store node pointers is not allowed, why is using recursion allowed? It uses stack implicitly and uses way more storage than a queue that stores node pointers.

Comment hidden because of low score. Click to expand.
0

@Anonymous:

Hasn't the stack already been allocated for you? All a stack allocation does is to decrement (or increment) the stack pointer...

Comment hidden because of low score. Click to expand.
0

@anonymous:
Doing an inorder traversal either using system stack or external stack is guranteed to occur otherwise how do we traverse the tree in the very first place? (just give it a thought)

I think what we need to pay attention is not using any space other than this implicit usage in the in-order traversal.

The idea/approach is that you keep doing in-order traversal and keep maintaining a previous pointer to figure out if my current node is equal to the previous node or not.

And the complexity of this algo would be o(n) same as we mention/consider for all the traversals of the tree.

Comment hidden because of low score. Click to expand.
0

@mr. Your first paragraph does not make much sense. Can you please clarify?

btw, we can traverse the tree in O(1) space, without recursion and using externals stacks, if the tree is threaded.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

You are not passing the count when you are calling the method recursively. How will this work ?

Comment hidden because of low score. Click to expand.
0

no need to pass the variable 'count'

``````int count_dup(node *root)
{
static int count;
....
....
return count;
}``````

Comment hidden because of low score. Click to expand.
0

OK. I am not a 'C' guy. May be it works.

Comment hidden because of low score. Click to expand.
0

Corrected.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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))
{
count = 0;
}

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

Comment hidden because of low score. Click to expand.
0

You can't use hashset or hashmap. Not supposed to use extra space. my bad, I should have mentioned in question. sorry

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

It basically if (inserting-data < parent) go left else if(inserting-data >= parent) go right

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

If you apply a constraint that prohibits duplicates you are correct, but a valid BST can have duplicates, which may reside deeper in the tree than the root.

Comment hidden because of low score. Click to expand.
0

No extra space i.e. queue shouldn't be there

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

Please post algorithm when you explain solution. Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Little more clarity: tree can't be modified. No extra space should be used. It should be O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) Solution?????

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0

You are printing all the counts individually, but how do you return or print the total duplicate count at end ? or return it ?

Comment hidden because of low score. Click to expand.
0

Duplicates can appear on either a right or left sub tree. See the example tree of this problem you will see there are 2 instances of dups on a left sub tree.

Comment hidden because of low score. Click to expand.
0

@Joe coder: you are right.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

find inorder successor for each node...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

Here is the stack implementation:

``````public int getDuplCountStack(TreeNode t) {
int count = 0;
Stack<TreeNode> parents = new Stack<TreeNode>();
TreeNode prev = null;

while (t != null || !parents.isEmpty()) {
if (t == null) {
t = parents.pop();

if (prev != null && t.data = prev.data)
count++;

prev = t;
t = t.right;
} else {
parents.push(t);
t = t.left;
}
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.