Java solution using BST, with explanation, beats 99% at time of posting
The idea is to use a BST to store the stream of integers. When adding nodes to the tree, we keep a pointer to the median node (middle node if odd number of elem
The idea is to use a BST to store the stream of integers. When adding nodes to the tree, we keep a pointer to the median node (middle node if odd number of elements, smaller of the two middle nodes if even number of elements).\n\nTwo helper functions - getNext and getPrev, allow us to update the median node.\n\nWhen should the median node be updated? Only two cases, both considering we have just added a node to the BST:\n\n1) We have an even number of elements, and the value added was less than the median value.\n\n2) We have an odd number of elements, and the value added was higher or equal to the median value.\n\n```\nclass Node {\n    int val;\n    Node right;\n    Node left;\n    Node parent;\n    public Node(int val){this.val = val;}\n}\n\npublic class MedianFinder {\n    Node tree;\n    Node medianNode;\n    int numElements = 0;\n    boolean addedLower = false;\n    \n    // Adds a number into the data structure.\n    public void addNum(int num) {\n        Node newNode = new Node(num);\n        addNode(tree, newNode);\n        numElements++;\n        if (num < medianNode.val){\n            addedLower = true;\n        } else {\n            addedLower = false;\n        }\n        updateMedianNode();\n    }\n\n    // Returns the median of current data stream\n    public double findMedian() {\n        // even number of elements\n        if (numElements % 2 == 0){\n            double num1 = medianNode.val;\n            double num2 = getNext(medianNode).val;\n            return (num1+num2)/2.0;\n        }\n        // odd number of elements\n        return medianNode.val;\n    }\n    \n    // add node to BST\n    private void addNode(Node curr, Node newNode){\n        if (curr == null){\n            tree = newNode;\n            medianNode = tree;\n            return;\n        }\n        if (curr.val > newNode.val){\n            if (curr.left == null){\n                curr.left = newNode;\n                curr.left.parent = curr;\n            } else {\n                addNode(curr.left, newNode);\n            }\n        } else if (curr.val <= newNode.val){\n            if (curr.right == null){\n                curr.right = newNode;\n                curr.right.parent = curr;\n            } else {\n                addNode(curr.right, newNode);   \n            }\n        }\n    }\n    \n    // keep pointing to median\n    private void updateMedianNode(){\n        if (numElements == 1){\n            return;\n        }\n        if (addedLower && numElements % 2 == 0){\n            medianNode = getPrev(medianNode);\n            return;\n        }\n        if (!addedLower && numElements % 2 == 1){\n            medianNode = getNext(medianNode);\n        }\n    }\n    \n    // get the inorder succesor\n    private Node getNext(Node curr){\n        if (curr.right != null){\n            curr = curr.right;\n            while (curr.left != null){\n                curr = curr.left;\n            }\n            return curr;\n        } else {\n            Node parent = curr.parent;\n            while (parent != null && parent.left != curr){\n                curr = parent;\n                parent = curr.parent;\n            }\n            return parent;\n        }\n        \n    }\n    \n    // get the inorder predecessor\n    private Node getPrev(Node curr){\n        if (curr.left != null){\n            curr = curr.left;\n            while (curr.right != null){\n                curr = curr.right;\n            }\n            return curr;\n        } else {\n            Node parent = curr.parent;\n            while (parent != null && parent.right != curr){\n                curr = parent;\n                parent = curr.parent;\n            }\n            return parent;\n        }\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();\n```
[]