[Javascript] AVL Tree(Set)- Self Balancing BST solution
Yea so if you wanna do this in js with the optimal time complexity you\'re in a bit of a pickle because you probably have to create your own AVL/ RedBlack tree 
Yea so if you wanna do this in js with the optimal time complexity you\'re in a bit of a pickle because you probably have to create your own AVL/ RedBlack tree class. What these trees offer is simple. These are containers of unique elements that are always sorted and balance themselves after each operation. Insertion,deletion and traversal all take O(logN) as a result.\nIn our problem, the first observation that needs to be made is that, since the queries are given a priori, we can process them in any order we desire. This is important, because if we process them by descending size and in parallel with the available rooms (also in the same order), we essentially remove the first constraint that, for any query [id,minsize] the only rooms that are considered have bigger sizes. \nWhat\'s now left is to pick the room with the closest id to the query\'s id. This is where the AVL tree will come in handy. Given that all the ids inside the tree are already sorted, we can traverse them exploiting the BST nature of the tree. As a result, finding the next bigger and next smaller element inside the tree is simply a walk down the tree starting from the root. Both of these functionalities are abstracted inside the class AVL for ease of use.\n\n```\nclass Node{\n    constructor(val,left=null,right=null,parent=null,bf=0,height=0){\n        this.val=val\n        this.left=left,this.right=right,this.parent=parent\n        this.bf=bf,this.height=height\n    }\n}\n\n// CAN ONLY STORE UNIQUE VALUES\nclass AVL{\n    constructor(){\n        this.nodeCount=0\n        this.root=null\n    }\n//===M O D I F Y   FOR     COMPLEX     NODES==\\\\\n    NODIFY(val){  //should return a new node based on the stats given\n        return new Node(val)\n    }\n    comparator=(node1,node2)=>{// basic comparator that returns <0,0,>0 if node1>node2,node1==node2,node1<node2\n        return node1.val-node2.val\n    }\n//-------------U S A B L E------------------\\\\\n    //returns true if the value was inserted successfully\n    //returns false if the value already exists\n    insert(NODE){ //O(logn) \n        if(NODE===null)\n            return false\n        NODE=this.NODIFY(NODE)\n        if(!this.contains(this.root,NODE)){\n            this.root=this.ins(this.root,NODE)\n            this.nodeCount++\n            return true\n        }\n        return false\n    }\n    remove(NODE){ \n        if(NODE===null)\n            return false\n        NODE=this.NODIFY(NODE)\n       // console.log(this.contains(this.root,new Node(7)))\n        if(this.contains(this.root,NODE)){\n            this.root=this.rem(this.root,NODE)\n            this.nodeCount--\n            return true\n        }\n        return false\n        //rebalance the tree\n    }\n    has(NODE){\n        NODE=this.NODIFY(NODE)\n        return this.contains(this.root,NODE)\n    }\n    traversalASC(){ //O(n)\n        let result=[]\n        let dfs=(node)=>{\n            if(!node)\n                return\n            dfs(node.left)\n            result.push(node)\n            dfs(node.right)\n        }\n        dfs(this.root)\n        return result\n    }\n    findNextSmaller(NODE){\n        NODE=this.NODIFY(NODE)\n        let cur=this.root,result=null\n        while(cur!==null){\n            if(this.comparator(cur,NODE)<0)\n                result=cur,\n                cur=cur.right\n            else\n                cur=cur.left\n        }\n        if(result===null)\n            return false // no such element\n        return result\n    }\n    findNextBigger(NODE){\n        NODE=this.NODIFY(NODE)\n        let cur=this.root,result=null\n        while(cur!==null){\n            if(this.comparator(cur,NODE)<=0)\n                cur=cur.right\n            else\n                result=cur,\n                cur=cur.left\n        }\n        if(result===null)\n            return false // no such element\n        return result\n    }\n//--------- I N T E R N A L S -----------------\\\\\n      contains(node,val){\n        if(node===null)\n            return false\n        let compare=this.comparator(node,val)\n        if(compare<0) //node<val\n            return this.contains(node.right,val)\n        if(compare>0)\n            return this.contains(node.left,val)\n        return true\n    }\n    //inserts newNode to target node\n    ins(tree,value){\n        if(tree===null)\n            return value\n        //(target is bigger? insert it to the left): else to the right\n        if(this.comparator(tree,value)>0)\n            tree.left=this.ins(tree.left,value)\n        else\n            tree.right=this.ins(tree.right,value)\n        //update balance factor of the target\n        this.update(tree) \n        return this.rebalance(tree) //balance the target if it needs rebalancing\n    }\n    rem(node,elem){\n        if(node===null)\n            return null\n        //search an existing node with the given value\n        let compare=this.comparator(elem,node)//-----\n        if(compare<0)\n            node.left=this.rem(node.left,elem)\n        else if(compare>0)\n            node.right=this.rem(node.right,elem)\n        else{ //node found\n             //remove the node and replace it with its sucessor\n            if(node.left===null)\n                return node.right\n            else if(node.right===null)\n                return node.left\n            else{ //still has both subtrees? \n                if(node.left.height>node.right.height){\n                    let successor=this.findMax(node.left)/////\n                    node.left=this.rem(node.left,successor)\n                }   \n                else{\n                    let successor=this.findMin(node.right)\n                    node.right=this.rem(node.right,successor)\n                }\n            }\n        }\n        this.update(node)\n        return this.rebalance(node)\n    }\n    //find the min and max node of the subtree rooted at (node)\n    findMin=(node)=>node.left?this.findMin(node.left):node\n    findMax=(node)=>node.right?this.findMax(node.right):node\n    //balances the subtree rooted at node if it is imbalanced (has balancefactor=+-2)\n    //and returns the now balanced node\n    rebalance(node){  //4 cases, 4 rotations\n        if(node.bf==-2){\n            if(node.left.bf<=0)\n                return this.LL(node)\n            else\n                return this.LR(node)\n        }\n        else if(node.bf==2){\n            if(node.right.bf>=0)\n                return this.RR(node)\n            else\n                return this.RL(node)\n        }\n        return node\n    }\n    //update the balance factor and the height of the current node\n    update(node){ \n        let leftHeight=node.left!==null?node.left.height:-1,rightHeight=node.right!==null?node.right.height:-1\n        node.height=Math.max(leftHeight,rightHeight)+1\n        node.bf=rightHeight-leftHeight\n    }\n\n    //4 cases of unbalanced trees\n    LL=(node)=>this.rightRotation(node)\n    RR=(node)=>this.leftRotation(node)\n    LR(node){\n        node.left=this.leftRotation(node.left)\n        return this.LL(node)\n    }\n    RL(node){\n        node.right=this.rightRotation(node.right)\n        return this.RR(node)\n    }\n    //2 total rotations that work on RR and LL cases\n    leftRotation(node){\n        let newParent=node.right\n        node.right=newParent.left\n        newParent.left=node\n        this.update(node)\n        this.update(newParent)\n        return newParent\n    }\n    rightRotation(node){\n        let newParent=node.left\n        node.left=newParent.right\n        newParent.right=node\n        this.update(node)\n        this.update(newParent)\n        return newParent\n    }\n\n}\n\n\nvar closestRoom = function(R, Q) {\n    let A=new AVL(),result=[...Array(Q.length)]\n    Q=Q.map((d,i)=>d.concat([i])) // save the original index in each query\n    R.sort((a,b)=>a[1]-b[1]) //sort everything in ascending Size\n    Q.sort((a,b)=>a[1]-b[1])\n    while(Q.length){\n\t    let [id,size,index]=Q.pop() //we re about to answer the biggest size query\n        while(R.length>0 && size<=R[R.length-1][1]) //so make anything with bigger size available\n            A.insert(R.pop()[0])\n        let nextsmaller=A.findNextSmaller(id),nextbigger=A.findNextBigger(id)\n        if(A.has(id))// the element exists inside the tree\n            result[index]=id\n        else if(nextsmaller!==false||nextbigger!==false ){\n            if(nextsmaller===false)\n                result[index]=nextbigger.val\n            else if(nextbigger===false)\n                result[index]=nextsmaller.val\n            else{//always pick the smallest abs distance\n                let d1=Math.abs(id-nextsmaller.val),d2=Math.abs(id-nextbigger.val)\n                if(d1<=d2)\n                    result[index]=nextsmaller.val\n                else\n                    result[index]=nextbigger.val\n            }\n        }\n        else\n            result[index]=-1\n    }\n    return result\n};\n```
['JavaScript']