[Java] Elegant O(log M)-add O(1)-avg TreeSet Solution
Thanks to the suggestion by @anindya-saha; Here is a very elegant Solution. The solution works great in these questions: \n 295. Find Median from Data Stream\n 
Thanks to the suggestion by @anindya-saha; Here is a very elegant Solution. The solution works great in these questions: \n* [295. Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/discuss/1246287/Java-clean-O(logN)-TreeSet-Solution-oror-with-comments)\n* [1825. Finding MK Average](https://leetcode.com/problems/finding-mk-average/discuss/1222887/Java-Elegant-O(log-M)-add-O(1)-avg-TreeSet-Solution)\n```\nclass MKAverage {\n    class Node implements Comparable<Node> {\n        int val;\n        int time;\n        \n        Node(int val, int time) {\n            this.val = val;\n            this.time = time;\n        }\n        \n        @Override\n        public int compareTo(Node other) {\n            return (this.val != other.val ? this.val - other.val \n                                          : this.time - other.time);\n        }\n    }\n    \n    private TreeSet<Node> set = new TreeSet<>();          // natural order\n    private Deque<Node> queue = new LinkedList<>();\n    private Node kLeft;\n    private Node kRight;\n    \n    private int m, k;\n    \n    private int time = 0;\n    private int sum = 0;\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n    }\n    \n    public void addElement(int num) {\n        Node node = new Node(num, time++);\n\n        addNode(node);\n        removeNode();\n        \n        if (time == m) init();\n    }\n    \n    private void init() {\n        int i = 0;\n        for (Node node : set) {\n            if (i < k-1);\n            else if (i == k-1) kLeft = node;\n            else if (i < m-k) sum += node.val;\n            else if (i == m-k) {\n                kRight = node;\n                return;\n            }\n            \n            i++;\n        }\n        return;\n    }\n    \n    private void addNode(Node node) {\n        queue.offerLast(node);\n        set.add(node);\n        \n        if (queue.size() <= m) return;\n        \n        if (node.compareTo(kLeft) < 0) {\n            sum += kLeft.val;\n            kLeft = set.lower(kLeft);\n        } else if (node.compareTo(kRight) > 0) {\n            sum += kRight.val;\n            kRight = set.higher(kRight);\n        } else {\n            sum += node.val;\n        } \n    }\n    \n    private void removeNode() {\n        if (queue.size() <= m) return;\n        \n        Node node = queue.pollFirst();\n        \n        if (node.compareTo(kLeft) <= 0) {\n            kLeft = set.higher(kLeft);\n            sum -= kLeft.val;\n        } else if (node.compareTo(kRight) >= 0) {\n            kRight = set.lower(kRight);\n            sum -= kRight.val;\n        } else {\n            sum -= node.val;\n        }\n        \n        set.remove(node);\n    }\n    \n    public int calculateMKAverage() {\n        return (queue.size() < m ? -1 : sum / (m - 2 * k));\n    }\n}\n```\n\n**Original Post:** \n```\nclass MKAverage {\n    class Node {\n        int val;\n        int time;\n        Node(int val, int time) {\n            this.val = val;\n            this.time = time;\n        }\n    }\n    \n    private TreeSet<Node> set; \n    private Deque<Node> queue;\n    private Node kLeft;\n    private Node kRight;\n    \n    int m;\n    int k;\n    \n    int time;\n    int sum;\n\n    public MKAverage(int m, int k) {\n        this.set = new TreeSet<>((a,b) -> (a.val != b.val) ? a.val - b.val : a.time - b.time);\n        this.queue = new LinkedList<>();\n        this.m = m;\n        this.k = k;\n        \n        this.time = 0;\n        this.sum = 0;\n    }\n    \n    public void addElement(int num) {\n        Node node = new Node(num, time++);\n\n        addNode(node);\n        removeNode();\n        \n        if (time == m) init();\n    }\n    \n    private void init() {\n        int i = 0;\n        for (Node node : set) {\n            if (i < k-1);\n            else if (i == k-1) kLeft = node;\n            else if (i < m-k) sum += node.val;\n            else if (i == m-k) {\n                kRight = node;\n                return;\n            }\n            \n            i++;\n        }\n        return;\n    }\n    \n    private void addNode(Node node) {\n        queue.offerLast(node);\n        set.add(node);\n        \n        if (queue.size() <= m) return;\n        \n        if (node.val < kLeft.val) {\n            sum += kLeft.val;\n            kLeft = set.lower(kLeft);\n        } else if (node.val >= kRight.val) {\n            sum += kRight.val;\n            kRight = set.higher(kRight);\n        } else {\n            sum += node.val;\n        } \n    }\n    \n    private void removeNode() {\n        if (queue.size() <= m) return;\n        \n        Node node = queue.pollFirst();\n        \n        if (node.val < kLeft.val || (node.val == kLeft.val && node.time <= kLeft.time)) {\n            kLeft = set.higher(kLeft);\n            sum -= kLeft.val;\n        } else if (node.val > kRight.val || (node.val == kRight.val && node.time >= kRight.time)) {\n            kRight = set.lower(kRight);\n            sum -= kRight.val;\n        } else {\n            sum -= node.val;\n        }\n        \n        set.remove(node);\n    }\n    \n    public int calculateMKAverage() {\n        return (queue.size() < m ? -1 : sum / (m - 2 * k));\n    }\n}\n```
['Tree', 'Ordered Set', 'Java']