Лучше собирать html-строку при обходе DOM-дерева, а потом сразу заменить весь document.body.innerHTML. Так работа превратится в написание конечного автомата, который в зависимости от состояния будет дописывать в строку нужные открывающие и закрывающие теги.
Если же работать, используя методы DOM для перестроения дерева, алгоритм во много раз усложнится и скорость выполнения скрипта упадет.
Я писал модуль для WYSIWYG-редактора, который преобразует весь код в нормальное состояние, заменяя deprecated-теги соответствующими CSS-стилями, объединяя одинаковые подрядидущие теги, удаляя пустые теги и т.д., вышло чуть больше 1000 строк кода
пытался реализовывать разными способами, но в итоге остановился на конечном автомате, собирающем новый HTML-код в строку, основываясь на данных, полученных при обходе DOM дерева.