Проблема только в правильной подстановке [ul] и [/ul].
Перед выводом всего дерева определяешь переменную $current_level = 0 (исходя из того, что уровень любого элемента не меньше 1).
Ну и в цикле делаешь проверку, если cat_level текущего элемента больше, чем $current_level, выводишь [ul], если меньше, выводишь [/ul], если равен - ничего не выводишь. В конце работы над каждый элементом $current_level делаешь равным cat_level`у текущего элемента.