CareerCup

hash

Why not a BST?

because suppose there are many occurrence of an number in BST whenever you find first occurance you just terminate search operation right? so we cant find all occurance of number

It would be better if we used Counting sort to sort the data and also we keep the record of occurrence of element

we can create a structure like this
struct node{
int n;
int count;
struct node *left;
struct node *right;
};
then we will create a bst
whenever the element will be encountered for the first time then it will be added to the best else the count will be incremented for that particular element

/// Using BST Method

struct Node
{
    int val;
    int cnt;
    Node * left;
    Node * right;
    Node(int v = 0, int n = 1) : val(v), cnt(n), left(NULL), right(NULL)
    {
    }
};
Node * insert_bst(Node * root, int v)
{
    if(NULL == root) {
        Node * r = new Node(v);
        return r;
    }
    Node * cur = root;
    while(cur) {
        if(cur->val == v) {
            cur->cnt ++;
            break;
        }
        else if(cur->val < v) {
            if(NULL == cur->right) {
                cur->right = new Node(v);
                break;
            }
            cur = cur->right;
        }
        else {
            if(NULL == cur->left) {
                cur->left = new Node(v);
                break;
            }
            cur = cur->left;
        }
    }
    return root;
}