/** * Internal method to remove from a subtree. * @param x the item to remove. * @param t the node that roots the tree. * @return the new root. * @throws ItemNotFoundException if x is not found. */ protected BinaryNode remove( AnyType x, BinaryNode t ) { if( t == null ) throw new ItemNotFoundException( x.toString( ) ); if( x.compareTo( t.element ) < 0 ) t.left = remove( x, t.left ); else if( x.compareTo( t.element ) > 0 ) t.right = remove( x, t.right ); else if( t.left != null && t.right != null ) // Two children { t.element = findMin( t.right ).element; t.right = removeMin( t.right ); } else t = ( t.left != null ) ? t.left : t.right; return t; } protected BinaryNode remove( AnyType x ) { if( x.compareTo( element ) < 0 ) { left = left.remove( x ); return this; } if( x.compareTo( element ) > 0 ) { right = right.remove( x ); return this; } if( left != null && right != null ) // Two children { element = right.findMin(); right = right.remove( element ); return this; } if (left == null) return right if (right == null) return left; }