22ms Java solution using binary tree, beats 99.82% of submissions
Some notes: This solution uses an ordinary binary tree for simplicity's sake, which means it is likely to be unbalanced. Given enough time one may well use a ba
**Some notes:** This solution uses an ordinary binary tree for simplicity's sake, which means it is likely to be unbalanced. Given enough time one may well use a balanced binary tree implementation to guarantee ```O(logn)``` runtime for ```addNum()```.  It is easy to see that ```findMedian()``` runs in ```O(1)```.\n\nBy using a binary tree, we can easily keep the input numbers in nondecreasing order. Observe that whenever a number is added, the numbers used to calculate the median never shift by more than 1 position (in an imagined array representation) to the left or to the right. Let's see an example:\n```[2]```, number used to calculate median is ```2```.\n```[2,3]```, numbers used are ```2,3``` (expanding 1 to right)\n```[0,2,3]```, use ```2``` (shrinking 1 to left)\n```[0,1,2,3]```, use ```1,2``` (expanding 1 to left)\n```[0,1,2,3,4]```, use ```2``` (shrinking 1 to right)\n....and so on.\n\nWith this observation, in ```MedianFinder``` I employ 2 variables ```medianLeft``` and ```medianRight``` to keep track of numbers we need to calculate the median. When ```size``` is odd, they point to the same node, otherwise they always point to 2 nodes which have predecessor/successor relationship. When adding a node, we just need to check the size of our ```MedianFinder``` tree, then depending on whether the new number is inserted to the left, inbetween, or to the right of our 2 median trackers, we will change ```medianLeft``` and ```medianRight``` to point to the correct nodes. Because the position never shifts more than 1, we can simply use ```predecessor()``` or ```successor()``` on the desired node to update it. Those 2 methods run in ```O(logn)``` when the tree is balanced, hence the ```O(logn)``` runtime of ```addNum()```.\n\nHope this helps!\n\n```\npublic class MedianFinder {\n    private Node root;\n    private Node medianLeft;\n    private Node medianRight;\n    private int size;\n    \n    public MedianFinder() {\n    }\n\n    // Adds a number into the data structure.\n    public void addNum(int num) {\n        if (root == null) {\n            root = new Node(num);\n            medianLeft = root;\n            medianRight = root;\n        }\n        else {\n            root.addNode(num);\n            if (size % 2 == 0) {\n                if (num < medianLeft.data) {\n                    medianRight = medianLeft;\n                }\n                else if (medianLeft.data <= num && num < medianRight.data) {\n                    medianLeft = medianLeft.successor();\n                    medianRight = medianRight.predecessor();\n                }\n                else if (medianRight.data <= num) {\n                    medianLeft = medianRight;\n                }\n            }\n            else {\n                if (num < medianLeft.data) {\n                    medianLeft = medianLeft.predecessor();\n                }\n                else {\n                    medianRight = medianRight.successor();\n                }\n            }\n        }\n        size++;\n    }\n\n    // Returns the median of current data stream\n    public double findMedian() {\n        return (medianLeft.data + medianRight.data) / 2.0;\n    }\n    \n    class Node {\n        private Node parent;\n        private Node left;\n        private Node right;\n        private int data;\n        \n        public Node(int data) {\n            this.data = data;\n        }\n        \n        public void addNode(int data) {\n            if (data >= this.data) {\n              if (right == null) {\n                right = new Node(data);\n                right.parent = this;\n              }\n              else\n                right.addNode(data);\n            }\n            else {\n              if (left == null) {\n                left = new Node(data);\n                left.parent = this;\n              }\n              else\n                left.addNode(data);\n            }\n        }\n        \n        public Node predecessor() {\n            if (left != null)\n                return left.rightMost();\n            \n            Node predecessor = parent;\n            Node child = this;\n            \n            while (predecessor != null && child != predecessor.right) {\n                child = predecessor;\n                predecessor = predecessor.parent;\n            }\n            \n            return predecessor;\n        }\n        \n        public Node successor() {\n            if (right != null)\n                return right.leftMost();\n            \n            Node successor = parent;\n            Node child = this;\n            \n            while (successor != null && child != successor.left) {\n                child = successor;\n                successor = successor.parent;\n            }\n            \n            return successor;\n        }\n        \n        public Node leftMost(){\n            if (left == null)\n                return this;\n            return left.leftMost();\n        }\n        \n        private Node rightMost() {\n            if (right == null)\n                return this;\n            return right.rightMost();\n        }\n        \n    }\n};\n```
['Binary Tree']