Recursive PseudoCode for BST            // NOT CAREFULLY VETTED YET.  BEWARE!!
                                        // REPAIRS FROM 10/17/2012 MADE
                                        // REPAIRS from 2/21/2013 MADE
                                        // REPAIR on 10.16/2018 MADE

/* BST nodes are type Node, which contains fields: int data, Node left, Node right */


/***********************************************************************************/
/* find value x in BST rooted at root */  

// example invocation:  foundNode = find(3, root);

Node find (int x, Node n) {
   if (n == null) return null;
	
   if (x == n.data) return n;
	
   else if (x < n.data) return find(x, n.left);
	
   else                                            // x > n.data
      return find(x, n.right);
}
	
	
/***********************************************************************************/
/* return reference to minimum value object in BST */

// example invocation: minNode = findMin(root);

Node findMin(Node n) {
   if (n == null)                                  // empty tree
      return null;
	
   if (n.left == null)
      return n;
		
   return findMin(n.left);
}


/***********************************************************************************/
/* insert  value x into BST*/

// example invocation:  root = insert( x, root); 

Node insert(int x, Node n) {
   if (n == null) {
      return (new Node(x, null, null));
   }
	
   else if (x <= n.data) {
      n.left = insert(x, n.left);
      return n;
   }
	
   else {                                           // x > n.data
      n.right = insert(x, n.right);
      return n;
   }
}
		

/***********************************************************************************/
/* delete (the first located) node containing value x from BST*/

// example invocation: root = delete(x, root);

Node delete(int x, Node n) {
   if (n == null)                                  // nothing to do
     return n;
	
   if (x == n.data) {                              // found first node containing x
		
      if (n.left == null && n.right == null)       // n is a leaf
         return null;                              // let garbage collector remove n
			
      else if (n.left == null) {                   // has right child only
         return n.right;
      }
			
      else if (n.right == null) {                  // has left child only
         return n.left;
      }
			
      else {                                       // has two children
         tempNode = findMin(n.right);
         n.data = tempNode.data;
         n.right = delete (tempNode.data, n.right);
         return n;
      }
   }                                               // end of found node containing x
		
   if (x <= n.data) {                              // still looking, go left
      n.left = delete(x, n.left);
      return n;
   }
	
   else  {                                         // still looking, go right
      n.right = delete(x, n.right);
      return n;
   }
}