use a self balancing binary search tree (BST) that has the same size (or off by one) left and right subtrees from the root getMedian: O(1) since the tree is balanced the median will always be the root node insert: O(logN) BST gives us logN insertion, balancing the tree is O(logN) as well and works in the following way: (this is only the most difficult case) if upon insertion the left subtree has two more nodes then the right subtree we need to rebalance the BST, that is take the largest value on the left subtree (rightmost node) and make that the new root, that works fine as this value is greater than everything on the left subtree and less than everything on the right subtree, then take the old root value and insert it in the right subtree, then the tree is balanced again and the median value is the root, ta-da! :)