title: Can someone explain Recursive delete() in Binary Search Tree and help me transform it
body: <p>I have as a form the code from Sedgewick's book called Algorithms:</p>
  
  <pre><code>    private Node deleteMin(Node x) {
          if (x.left == null) return x.right;
          x.left = deleteMin(x.left);
          x.N = size(x.left) + size(x.right) + 1;
          return x;
      }
  
      public void delete(Key key) {
          root = delete(root, key);
      }
  
      private Node delete(Node x, Key key) {
          if (x == null) return null;
          int cmp = key.compareTo(x.key);
          if      (cmp &lt; 0) x.left  = delete(x.left,  key);
          else if (cmp &gt; 0) x.right = delete(x.right, key);
          else { 
              if (x.right == null) return x.left;
              if (x.left  == null) return x.right;
              Node t = x;
              x = min(t.right);
              x.right = deleteMin(t.right);
              x.left = t.left;
          } 
          x.N = size(x.left) + size(x.right) + 1;
          return x;
      }
  </code></pre>
  
  <p>Basically I want to know how the recursion works in the tree, because I want to transform this method to when finding the node to rotate it until becomes a leaf and then delete it.</p>
  
  <pre><code>public void delete(Key key) {
          root = delete(root, key);
      }
  
      private Node delete(Node x, Key key) {
          if (x == null) return null;
          int cmp = key.compareTo(x.key);
          if      (cmp &lt; 0) x.left  = delete(x.left,  key);
          else if (cmp &gt; 0) x.right = delete(x.right, key);
          else { 
              //if is a leaf delete it
              //if has one child rotate it
              //if it has two children compare some value
              //of the children choose the bigger and rotate
  
          } 
          x.N = size(x.left) + size(x.right) + 1;
          return x;
      }
  
  private Node rotateLeft(Node h)
  {
      Node x = h.right;
      h.right = x.left;
      x.left = h;
  
      return x;
  }
  
  private Node rotateRight(Node h)
  {
      Node x = h.left;
      h.left = x.right;
      x.right = h;
  
      return x;
  }
  </code></pre>
  
  <p>I tried some things but it throws a null pointer exception. I've managed to do it iteratively but
  the pointers to the nodes aren't updated so I lose the tree. Can someone show me how it works so I can modify it properly?</p>