title: Cracking the Coding Interview 6th Edition: 10.10. Rank from Stream
body: <p>The problem statement is as follows:</p>
  <blockquote>
  <p>Imagine you are reading in a stream of integers. Periodically, you
  wish to be able to look up the rank of a number x (the number of
  values less than or equal to x). Implement the data structures and
  algorithms to support these operations.That is, implement the method
  track (in t x), which is called when each number is generated, and the
  method getRankOfNumber(int x) , which returns the number of values
  less than or equal to X (not including x itself).</p>
  <p>EXAMPLE: Stream(in order of appearance): 5, 1, 4, 4, 5, 9, 7, 13, 3</p>
  <p>getRankOfNumber(1) = 0 getRankOfNumber(3) = 1  getRankOfNumber(4) = 3</p>
  </blockquote>
  <p>The suggested solution uses a modified Binary Search Tree, where each node stores stores the number of nodes to the left of that node. The time complexity for both methods is is O(logN) for balanced tree and O(N) for unbalanced tree, where N is the number of nodes.</p>
  <p>But how can we construct a balanced BST from a stream of random integers? Won't the tree become unbalanced in due time if we keep on adding to the same tree and the root is not the median? Shouldn't the worst case complexity be O(N) for this solution (in which case a HashMap with O(1) and O(N) for track() and getRankOfNumber() respectively would be better)?</p>