categorias y subcategorias con una sola tabla

Estoy buscando la forma de hacer categorias y subcategorias solo con una tabla simple:

Código MySQL :

CREATE TABLE IF NOT EXISTS `categorias` (
  `categoria_id` bigint(200) NOT NULL AUTO_INCREMENT,
  `categoria_padre` int(15) DEFAULT NULL,
  `categoria_nombre` varchar(250) NOT NULL,
  PRIMARY KEY (`categoria_id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=3 ;

Obviamente categoría padre es NULL o el valor de la categoría superior.

Lo que no doy es con el script. Que necesito que lo ponga como lista:

Categoria
Sub
sub
Sub
Sud

Generé este codigo pero me da error y solo me muestra la primer letra de la categoria... AYUDAAAAAAAAAAAAA

Código PHP :

<?php
$categorias = mysql_query("SELECT * FROM categorias");

while ($categoria = mysql_fetch_assoc($categorias)) {
   $categoria['categoria_padre'] = NULL;
  if( $categoria['categoria_padre']== NULL ){
    $cate[$categoria['categoria_id']['super']] = $categoria['categoria_nombre'];
  }else{
    $cate[$categoria['categoria_padre']['sub']['categoria_id']] = $categoria['categoria_nombre'];
  } 
}
?> 
<li><a href="#">TIENDA ONLINE</a><span></span>
     <ul>
<?php foreach($cate as $k=>$c ){
        if(!array_key_exists($c,'sub')) {
            ?>
            <li><a href="#"><?php echo $c['super']?></a></li>
         <?php } else { ?>
            <li><a href="#"><?php echo $c['super']?></a>
                <ul>
                    <?php foreach($c['sub'] as $kk=>$cc){?>
                    <li><a href="#"><?php echo $cc ?></a></li>
               <?php } ?>
                </ul>
            </li>
         <?php
        }
}
?>
     </ul>
</li> 

Warning: array_key_exists() expects parameter 2 to be array, string given in C:\index.php on line 42

bueno, gracias igual

Amigo podrias poner un SQL con los datos.. es que la verdad me da flojera inventar datos.

sirve que te hago un ejemplo muy sencillo y ya lo adaptas a lo que necesitas.