TreeMap + Queue
https://carefree-ladka.github.io/js.enigma/docs/DSA/TreeMap
https://carefree-ladka.github.io/js.enigma/docs/DSA/TreeSet
https://carefree-ladka.github.io/js.enig
https://carefree-ladka.github.io/js.enigma/docs/DSA/TreeMap
https://carefree-ladka.github.io/js.enigma/docs/DSA/TreeSet
https://carefree-ladka.github.io/js.enigma/docs/DSA/SortedList

and many more ...  . I built this site to revsie topics for last minute . 

The implementation is quite efficient 

![image.png](https://assets.leetcode.com/users/images/e3ee7f91-6914-4786-aa1b-05313d3c9cb5_1736873037.707172.png)


---

```javascript []
class TreeNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}


class TreeMap {
  constructor() {
    this.root = null;
    this.size = 0;
  }

  // Get height of node
  #getHeight(node) {
    return node ? node.height : 0;
  }

  // Get balance factor
  #getBalance(node) {
    return node ? this.#getHeight(node.left) - this.#getHeight(node.right) : 0;
  }

  // Right rotation
  #rightRotate(y) {
    const x = y.left;
    const T2 = x.right;

    x.right = y;
    y.left = T2;

    y.height = Math.max(this.#getHeight(y.left), this.#getHeight(y.right)) + 1;
    x.height = Math.max(this.#getHeight(x.left), this.#getHeight(x.right)) + 1;

    return x;
  }

  // Left rotation
  #leftRotate(x) {
    const y = x.right;
    const T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = Math.max(this.#getHeight(x.left), this.#getHeight(x.right)) + 1;
    y.height = Math.max(this.#getHeight(y.left), this.#getHeight(y.right)) + 1;

    return y;
  }

  // Insert a key-value pair
  put(key, value) {
    this.root = this.#put(this.root, key, value);
    return this;
  }

  #put(node, key, value) {
    if (!node) {
      this.size++;
      return new TreeNode(key, value);
    }

    if (key < node.key) {
      node.left = this.#put(node.left, key, value);
    } else if (key > node.key) {
      node.right = this.#put(node.right, key, value);
    } else {
      node.value = value; // Update value if key exists
      return node;
    }

    node.height = Math.max(this.#getHeight(node.left), this.#getHeight(node.right)) + 1;

    const balance = this.#getBalance(node);

    // Left Left Case
    if (balance > 1 && key < node.left.key) {
      return this.#rightRotate(node);
    }

    // Right Right Case
    if (balance < -1 && key > node.right.key) {
      return this.#leftRotate(node);
    }

    // Left Right Case
    if (balance > 1 && key > node.left.key) {
      node.left = this.#leftRotate(node.left);
      return this.#rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && key < node.right.key) {
      node.right = this.#rightRotate(node.right);
      return this.#leftRotate(node);
    }

    return node;
  }

  // Get value by key
  get(key) {
    const node = this.#get(this.root, key);
    return node ? node.value : undefined;
  }

  #get(node, key) {
    if (!node) return null;
    if (key === node.key) return node;
    return key < node.key ? this.#get(node.left, key) : this.#get(node.right, key);
  }

  // Remove key-value pair
  remove(key) {
    const hasKey = this.has(key);
    if (hasKey) {
      this.root = this.#remove(this.root, key);
      this.size--;
    }
    return hasKey;
  }

  #remove(node, key) {
    if (!node) return null;

    if (key < node.key) {
      node.left = this.#remove(node.left, key);
    } else if (key > node.key) {
      node.right = this.#remove(node.right, key);
    } else {
      if (!node.left || !node.right) {
        return node.left || node.right;
      }

      const successor = this.#getMin(node.right);
      node.key = successor.key;
      node.value = successor.value;
      node.right = this.#remove(node.right, successor.key);
    }

    node.height = Math.max(this.#getHeight(node.left), this.#getHeight(node.right)) + 1;

    const balance = this.#getBalance(node);

    // Rebalance after removal
    if (balance > 1 && this.#getBalance(node.left) >= 0) {
      return this.#rightRotate(node);
    }
    if (balance > 1 && this.#getBalance(node.left) < 0) {
      node.left = this.#leftRotate(node.left);
      return this.#rightRotate(node);
    }
    if (balance < -1 && this.#getBalance(node.right) <= 0) {
      return this.#leftRotate(node);
    }
    if (balance < -1 && this.#getBalance(node.right) > 0) {
      node.right = this.#rightRotate(node.right);
      return this.#leftRotate(node);
    }

    return node;
  }

  // Check if key exists
  has(key) {
    return this.#get(this.root, key) !== null;
  }

  // Get minimum key
  firstKey() {
    if (!this.root) return undefined;
    return this.#getMin(this.root).key;
  }

  // Get maximum key
  lastKey() {
    if (!this.root) return undefined;
    return this.#getMax(this.root).key;
  }

  #getMin(node) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  #getMax(node) {
    while (node.right) {
      node = node.right;
    }
    return node;
  }

  // Get first key greater than or equal to given key
  ceilingKey(key) {
    let node = this.root;
    let ceiling = null;

    while (node) {
      if (key === node.key) {
        return key;
      }
      if (key < node.key) {
        ceiling = node.key;
        node = node.left;
      } else {
        node = node.right;
      }
    }

    return ceiling;
  }

  // Get last key less than or equal to given key
  floorKey(key) {
    let node = this.root;
    let floor = null;

    while (node) {
      if (key === node.key) {
        return key;
      }
      if (key < node.key) {
        node = node.left;
      } else {
        floor = node.key;
        node = node.right;
      }
    }

    return floor;
  }

  // Clear all entries
  clear() {
    this.root = null;
    this.size = 0;
  }

  // Get size of tree
  getSize() {
    return this.size;
  }

  // Check if tree is empty
  isEmpty() {
    return this.size === 0;
  }

  // Get all keys in order
  keys() {
    const result = [];
    this.#inorderTraversal(this.root, node => result.push(node.key));
    return result;
  }

  // Get all values in order of keys
  values() {
    const result = [];
    this.#inorderTraversal(this.root, node => result.push(node.value));
    return result;
  }

  // Get all entries in order
  entries() {
    const result = [];
    this.#inorderTraversal(this.root, node => result.push([node.key, node.value]));
    return result;
  }

  #inorderTraversal(node, callback) {
    if (node) {
      this.#inorderTraversal(node.left, callback);
      callback(node);
      this.#inorderTraversal(node.right, callback);
    }
  }
}

class MKAverage {
  constructor(m, k) {
    // Initialize parameters
    this.m = m;
    this.k = k;
    this.total = 0;

    // Queue to maintain the last m elements
    this.queue = [];

    // TreeMap to maintain sorted elements with their frequencies
    this.countMap = new TreeMap();
  }

  addElement(num) {
    this.queue.push(num);
    this.#addToMap(num);

    // Remove oldest element if window size exceeds m
    if (this.queue.length > this.m) {
      const oldNum = this.queue[this.queue.length - this.m - 1];
      this.#removeFromMap(oldNum);
    }
  }

  // Helper method to add number to TreeMap
  #addToMap(num) {
    const count = this.countMap.get(num) || 0;
    this.countMap.put(num, count + 1);
    this.total += num;
  }

  // Helper method to remove number from TreeMap
  #removeFromMap(num) {
    const count = this.countMap.get(num);
    if (count === 1) {
      this.countMap.remove(num);
    } else {
      this.countMap.put(num, count - 1);
    }
    this.total -= num;
  }

  calculateMKAverage() {
    // Return -1 if we don't have enough elements
    if (this.queue.length < this.m) {
      return -1;
    }

    let remainSum = this.total;
    let remainCount = this.m;
    let currentK = this.k;

    // Remove k smallest elements
    const entries = this.countMap.entries();
    let i = 0;
    while (currentK > 0 && i < entries.length) {
      const [num, count] = entries[i];
      const toRemove = Math.min(currentK, count);
      remainSum -= num * toRemove;
      remainCount -= toRemove;
      currentK -= toRemove;
      i++;
    }

    // Remove k largest elements
    currentK = this.k;
    i = entries.length - 1;
    while (currentK > 0 && i >= 0) {
      const [num, count] = entries[i];
      const toRemove = Math.min(currentK, count);
      remainSum -= num * toRemove;
      remainCount -= toRemove;
      currentK -= toRemove;
      i--;
    }

    // Calculate average of remaining elements
    return Math.floor(remainSum / remainCount);
  }
}
```
['Design', 'Queue', 'Data Stream', 'Ordered Set', 'JavaScript']