Имхо, лучше пусть в памяти хранятся — перерисовка с нуля будет еще тяжелее
Кстати, советую попробовать обойтись без removeChild. Можно просто скрывать ветку, не удаляя ее, используя style.
Т.о. и дерево будет целое и нагрузка поменьше.