Java Solution with Tree - O(Log N) Insertion and Lookup + Explanation
The intution behind the solution is pretty straightforward. We will get a random stream of numbers. We want to repeateadly find median from this stream. \nThis 
The intution behind the solution is pretty straightforward. We will get a random stream of numbers. We want to repeateadly find median from this stream. \nThis tells us we need to store the numbers sorted in some DS where insert and find middle is fairly quick. This leads me to Priority Queue and Tree. \n\nI personally prefered implementing Tree since Queue solution felt quiet simple to me and would not make an interviewer very happy (IMHO).\n\nNow I am adding 2 extra fields at every node along with the usual value, left and right: leftCount, rightCount. This helps me in findMedian if i want to get to index 5 and root\'s left has 2 nodes i can just go to right directly.\n\nNode object used for Tree:\n\n```private class Node {\n        private int value;\n        private Node left;\n        private Node right;\n        private int leftCount;\n        private int rightCount;\n\n        public Node(int value) {\n            this.value = value;\n        }\n    }\n```\n\nAdd an element:\nWe compare to root and then either go left or right depending on value comparison. Whichever direction we go, we increment the counter.\n\n```\n    private Node root;\n    public void addNum(int num) {\n        if (root == null) {\n            root = new Node(num);\n        } else {\n            addNode(root, num);\n        }\n    }\n\t\n\tprivate void addNode(Node root, int num) {\n        if (root.value < num) {\n            root.rightCount++;\n            if (root.right == null) {\n                root.right = new Node(num);\n            } else {\n                addNode(root.right, num);\n            }\n        } else {\n            root.leftCount++;\n            if (root.left == null) {\n                root.left = new Node(num);\n            } else {\n                addNode(root.left, num);\n            }\n        }\n    }\n```\n\t\nFind Median:\nWe keep an indexSoFar variable which tells us the current node index if left==null. \n```\npublic double findMedian() {\n        if (root == null) {\n            throw new RuntimeException("No element present");\n        }\n\n        int size = root.leftCount + root.rightCount + 1;\n        double value;\n        if (size % 2 == 0) {\n            value = (double) findNode(size / 2 - 1) / 2;\n            value += (double) findNode(size / 2) / 2;\n        } else {\n            value = findNode(size / 2);\n        }\n\n        return value;\n    }\n\t\n\tprivate int findNode(int indexToReturn) {\n        int indexSoFar = 0;\n        Node node = root;\n\n        while (node != null) {\n\t\t   // Reached Index, return current\n            if (indexSoFar + node.leftCount == indexToReturn) {\n                return node.value;\n            } \n\t\t\t// Index is on left, go to left\n\t\t\telse if (indexSoFar + node.leftCount > indexToReturn) {\n                node = node.left;\n            } \n\t\t\t// Index is on right, go to right\n\t\t\telse {\n                indexSoFar += node.leftCount + 1;\n                node = node.right;\n            }\n        }\n\n        // This should never happen\n        throw new RuntimeException("Something is wrong with FindNode. Looking for index: " + indexToReturn);\n    }\n```\n\nA few improvisations can be done to make findMedian O(1):\n- Tree can be rebalanced perodically - maybe asyncronously. This will bring median much closer to root.\n- Do not necessarily need to keep right count. That can be removed if we keep size variable at global level.\n- For even scenarios we can optimize so we dont have to perform find size/2-1 and size/2 seperately - fairly straightforward.
['Tree', 'Depth-First Search']