title: insert function for a preorder threaded binary search tree
body: <p>I'm trying to make a tree, in a way such that the left child of a terminal(leaf node) node.<br>
  <a href="http://4.bp.blogspot.com/-t4FC1qhbAe4/UrcK6QapPoI/AAAAAAAAAIs/aiKZBm2KK9k/s1600/preorder+traversal+of+Binary+tree.png" rel="nofollow noreferrer">link to see what tree should look like.</a>  </p>
  
  <p>I've gotten an inorder version of the code i want, its a simple insert function that threads the tree ,but now my problem is changing this code into a preOrder insert.  </p>
  
  <p>This i can do, but my main problem is finding the preorder successor, which is all the way in a other sub tree, do any of you guys know a simple way to get the preorder successor?</p>
  
  <pre><code>//in-order insert
  if (root == null) {                  // tree is empty
      root = newNode;
      return;
  }
  PreNode&lt;T&gt; p = root, prev = null;
      while (p != null) {              // find a place to insert newNode;
      prev = p;
      if (info.compareTo(p.info) &lt; 0)
          p = p.left;
      else if (!p.hasThread)           // go to the right node only if it is
          p = p.right;                 // a descendant, not a successor;
      else break;                      // don't follow successor link;
  }
  
  if (info.compareTo(prev.info) &lt; 0) { // if newNode is left child of
      prev.left  = newNode;            // its parent, the parent becomes
      newNode.hasThread = true;        // also its successor;
      newNode.right = prev;
  }
  else if (prev.hasThread) {           // if parent of the newNode
      newNode.hasThread = true;        // is not the right-most node,
      prev.hasThread = false;          // make parent's successor
      newNode.right = prev.right;      // newNode's successor,
      prev.right = newNode;
  }
  else prev.right = newNode;           // otherwise has no successor;
  </code></pre>