CareerCup

confusing..

use BST and no recursion, no extra memory is allowed. - your BST will cost O(n) extra space

good question. It comes down to solving inorder without recursion and no extra space.

Threaded binary tree, basically..

The essence of the answer (assuming no extra memory apart from that used for the BST).

1. Take the first character of the string and make it the root
2. For every nth character, check if it is in the BST
i. If it is in BST, increment the counter.
ii. If it is not, insert it in the BST depending on its ASCII number
3. In the end do an inorder traversal of the BST

The main step is the second step, at worst you would do n searches of O(logn) and n insertions of O(logn) giving you the overall complexity of O(nlogn).

Sorry guys...no extra memory while contructing the BST. yes, definitely the BST is extra memory, but no more memory excpet this.

do an in place sort using the string (assuming its mutable)... voila

assuming 1 variable to hold the count, just one.

the bst will hold all the unique characters in the string.

so we parse the bst ( iterative inorder) and for each character we come across, we check the string for its occurrence and increment the count and spit the count alongside the character and move on to next character and reset the count -> 0

Yes, I agree with aatish.mandelecha, it has to be a threaded binary tree, and when you are inserting a duplicate entry, add it to the left subtree say X so that it will fall to the rightmost node in the right subtree of X. This will make that node immediate predecessor of the duplicate. Now you can print using inorder traversal using threads.

What I can think of is to add a count variable while declaring the struct for the node of the tree and then construct the binary tree and whenever the current letter from the string is already there in the tree, just increment the count of that node.

Do the inorder Traversal iteratively and print out the count along with the letter

What I can think of is to add a count variable while declaring the struct for the node of the tree and then construct the binary tree and whenever the current letter from the string is already there in the tree, just increment the count of that node.

Do the inorder Traversal iteratively and print out the count along with the letter

I think we need extra memory besides BST to keep track of the number of ocurrence(correct me if I am wrong). Here is my implementation without using recursion.

void PrintTree(node* root)
{
node* stack[256] = {0};
int top = 0;

if(!root)
return;

node* t = root;

while(t)
{
while(t)
{
stack[top++] = t;
t = t->left;
}

t = stack[--top];
if(a[t->data] > 0)
{
printf("%c", t->data);
printf("%d", a[t->data]);
a[t->data] = 0;
}

while(!t->right && top>0)
{
t = stack[--top];

if(a[t->data] > 0)
{
printf("%c", t->data);
printf("%d", a[t->data]);
a[t->data] = 0;
}
}

if(a[t->data] > 0)
{
printf("%c", t->data);
printf("%d", a[t->data]);
a[t->data] = 0;
}
t = t->right;
}
}