Given an array of integers, sort the array according to frequency of elements.

algo.md

-- create BST with freq property updated if duplicate is inserted

-- do inorder traversal and store the data and freq of each node in an auxiliary array count => [{data:data,freq:freq}]

-- sort the count array with descending frequency

-- traverse the array and print every data element in count count[i].freq times

sortByFrequency.js

class Node{
    constructor(data){
        this.data = data
        this.left = null
        this.right = null
        this.freq = 1
    }
}

class BST{
    constructor(){
        this.root = null
    }

    insert(node,data){
        if(node==null)return new Node(data);
        if(data == node.data)node.freq+=1;
        else if(data < node.data)node.left = this.insert(node.left,data);
        else node.right = this.insert(node.right,data);
        return node;
    }

    store(root,count){
        if(root==null)return;
        this.store(root.left,count);
        count.push({data:root.data,freq:root.freq});
        this.store(root.right,count);
    }

}

function sortByFrequency(arr=[]){
    let n = arr.length
    let tree = new BST();
    for(let i=0;i<n;i++){
        tree.root = tree.insert(tree.root,arr[i]);
    }
    let count = []
    tree.store(tree.root,count);
    count.sort((a,b) => {
        return b.freq - a.freq;
    })
    let j = 0
    for(let i=0;i<count.length;i++){
        for(let freq = count[i].freq;freq>0;freq--){
            arr[j++] = count[i].data
        }
    }
    console.log(arr)
}

sortByFrequency([2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12])