class TreeNode {    
     constructor(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
         this.height = 1
        this.count = 1; 
     }
     
 }

var MedianFinder = function() {
    this.root = null;
    this.size = 0;
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    this.root = insertIntoBST(this.root, num)
    console.log(this.root)
    this.size++;
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    if(this.root == null){
       return null;
       }else if(this.size % 2 == 0){  // if even
                    var valueFirst = (this.size/2) ;
                    var valueSecond = (this.size/2) +1;
                    return (kthSmallest(this.root, valueFirst) + kthSmallest(this.root, valueSecond))/2
                }else{                // if odd
                    var value = ((this.size - 1)/2) +1;
                    return kthSmallest(this.root, value);
                }
};


var rotateRight = function(y){
    var x = y.left;
    var t2 = x.right;
    x.right = y;
    y.left = t2;
    
    x.height = max(findHeight(x.left), findHeight(x.right)) +1;
    y.height = max(findHeight(y.left), findHeight(y.right)) +1;
    return x;
}
var rotateLeft= function(x){
    var y = x.right;
    var t2 = y.left;
    y.left = x;
    x.right = t2;
    
    x.height = max(findHeight(x.left), findHeight(x.right)) +1;
    y.height = max(findHeight(y.left), findHeight(y.right)) +1;  
    return y
}

var findHeight = function(node){
    if(node == null) return 0
    else return node.height;
    
}

var findBF = function(node){
    return findHeight(node.left) - findHeight(node.right)
}

    var max = function( a,  b)  
    {  
        return (a > b) ? a : b;  
    } 

var insertIntoBST = function(root, val) {      
    // regular insert
    if(root == null){       
       return new TreeNode(val)        
       }
    if (val == root.val) { 
    (root.count)++; 
    return root; 
       } 
        if (val < root.val) 
            root.left = insertIntoBST(root.left, val); 
        else
            root.right = insertIntoBST(root.right, val); 
    // go hard or go home
    root.height = 1 + max(findHeight(root.left),  
                            findHeight(root.right));  
    
    // check balence
    var bf = findBF(root);
    
    // rotation checks
    //LEFT rr
    if(bf > 1 && val < root.left.val){
        return rotateRight(root)
        }
     //RIGHT ll
     if(bf < -1 && val > root.right.val){
        return rotateLeft(root)
        }
     //LFThe 
     if(bf > 1 && val > root.left.val){
        root.left = rotateLeft(root.left)
         return rotateRight(root);
        }
     //RL
     if(bf < -1 && val < root.right.val){
        root.right = rotateRight(root.right);
         return rotateLeft(root);
        }
    return root
};


var kthSmallest = function(root, k) {
    let result = [];
    helper(root)
    return result[k - 1];
    
    function helper(node) {
        if (!node) return;
        if (result.length >= k) return;
        
        helper(node.left);
        if (result.length >= k) return;
        for(var i = 0; i < node.count; i++){
            result.push(node.val);
        }
        
        helper(node.right);
    }
};