title: understanding this recursive function in a BST tree
body: <p>I'm having a hard time understanding this code for the ranking of nodes by size. Rank returns the size of all the nodes less than the key. </p>
  
  <p><a href="http://algs4.cs.princeton.edu/32bst/BST.java.html" rel="nofollow">http://algs4.cs.princeton.edu/32bst/BST.java.html</a></p>
  
  <p>how is the result returned for rank(key, x.left)??? </p>
  
  <p>code: </p>
  
  <pre><code> public int rank(Key key) {
          return rank(key, root);
      } 
  
      // Number of keys in the subtree less than key.
      private int rank(Key key, Node x) {
          if (x == null) return 0; 
          int cmp = key.compareTo(x.key); 
          if      (cmp &lt; 0) return rank(key, x.left); 
          else if (cmp &gt; 0) return 1 + size(x.left) + rank(key, x.right); 
          else              return size(x.left); 
      }
  
  
   // is the symbol table empty?
      public boolean isEmpty() {
          return size() == 0;
      }
  
      // return number of key-value pairs in BST
      public int size() {
          return size(root);
      }
  
  // return number of key-value pairs in BST rooted at x
  private int size(Node x) {
      if (x == null) return 0;
      else return x.N;
  } 
  </code></pre>