18ms beats 100% Java Solution with BST
The method is vulnerable to (largely) monotonic inputs, which could push the complexity of addNum to O(n), resulting in "Time Limit Exceeded" errors.  At the ti
The method is vulnerable to (largely) monotonic inputs, which could push the complexity of `addNum` to O(n), resulting in "Time Limit Exceeded" errors.  At the time of the original post (back in 2016), there weren\'t such test cases.  I believe the "self-balancing binary search tree" would do the rescue.\n\n    class MedianFinder {\n        class TreeNode{\n            int val;\n            TreeNode parent,left,right;\n            TreeNode(int val, TreeNode p){\n                this.val=val;\n                this.parent=p;\n                left=null;\n                right=null;\n            }\n            void add(int num){\n                if(num>=val){\n                    if(right==null)\n                        right=new TreeNode(num,this);\n                    else\n                        right.add(num);\n                }else{\n                    if(left==null)\n                        left=new TreeNode(num,this);\n                    else\n                        left.add(num);\n                }\n            }\n            TreeNode next(){\n                TreeNode ret;\n                if(right!=null){\n                    ret=right;\n                    while(ret.left!=null)\n                        ret=ret.left;\n                }else{\n                    ret=this;\n                    while(ret.parent.right==ret)\n                        ret=ret.parent;\n                    ret=ret.parent;\n                }\n                return ret;\n            }\n            TreeNode prev(){\n                TreeNode ret;\n                if(left!=null){\n                    ret=left;\n                    while(ret.right!=null)\n                        ret=ret.right;\n                }else{\n                    ret=this;\n                    while(ret.parent.left==ret)\n                        ret=ret.parent;\n                    ret=ret.parent;\n                }\n                return ret;\n            }\n        }\n        int n;\n        TreeNode root, curr;\n        // Adds a number into the data structure.\n        public void addNum(int num) {\n            if(root==null){\n                root = new TreeNode(num,null);\n                curr=root;\n                n=1;\n            }else{\n                root.add(num);\n                n++;\n                if(n%2==1){\n                    if(curr.val<=num)\n                        curr=curr.next();\n                }else\n                    if(curr.val>num)\n                        curr=curr.prev();\n            }\n        }\n    \n        // Returns the median of current data stream\n        public double findMedian() {\n            if(n%2==0){\n                return ((double)curr.next().val+curr.val)/2;\n            }else\n                return curr.val;\n        }\n    };\n    \n    // Your MedianFinder object will be instantiated and called as such:\n    // MedianFinder mf = new MedianFinder();\n    // mf.addNum(1);\n    // mf.findMedian();
['Binary Search Tree', 'Java']