Solution using Binary Search Tree
As the input numbers are random, so the height of the binary search tree is O(logN)\n\nWe maintain every single node's children's size and it's easy to implemen
As the input numbers are random, so the height of the binary search tree is O(logN)\n\nWe maintain every single node's children's size and it's easy to implement because it just has add operation.\n\n    struct BST {\n        struct node {\n            int val;\n            int size;\n            node* left, *right;\n            node(int v) : size(1), val(v) {};\n        } *Null, *root;\n        \n        BST() {\n            Null = new node(0);\n            Null -> size = 0;\n            root = Null;\n        }\n        \n        void add(int val, node*& R) {\n            if(R == Null) {\n                R = new node(val);\n                R -> left = R -> right = Null;\n                return;\n            }\n            if(R->val <= val) add(val, R->left);\n            else add(val, R->right);\n            R->size = R->left->size + R->right->size + 1;\n            \n        }\n        \n        int rank(int k) {\n            node* t = root;\n            while(true) {\n                int leftSize =  t -> left -> size;\n                if(leftSize == k) return t -> val;\n                if(leftSize > k) {\n                    t = t -> left;\n                } else {\n                    k = k - leftSize - 1;\n                    t = t -> right;\n                }\n            }\n            return -1;\n        }\n    };\n    \n    \n    \n    \n    class MedianFinder {\n    public:\n        BST* bst;\n        MedianFinder() {\n            bst = new BST();\n        }\n        // Adds a number into the data structure.\n        void addNum(int num) {\n            bst->add(num, bst->root);\n        }\n        \n        // Returns the median of current data stream\n        double findMedian() {\n            int sz = bst -> root -> size;\n            if(sz % 2 == 0) {\n                return 1.0 * (bst -> rank(sz / 2) + bst -> rank(sz / 2 - 1)) / 2;\n            } else return bst->rank(sz / 2);\n            \n        }\n    };
['Binary Search', 'Tree', 'C++']