Нарисуй дерево на бумаге. Поставь слева от корня число 1.
Дальше вниз и влево, слева от этого 2 и так по левому краю. У самого нижнего справа его левое +1, обходишь также соседние ветки и всё дерево. Результат такой, что у ноды с дочерними левое число меньше всех чисел детей, а правое больше всех чисел детей, и левых, и правых.
Теперь чтобы выбрать детей любой ноды с ней или без нее надо сделать один запрос. Разница левого и правого позволяет понять количество детей. По левому удобно сортировать на том же уровне, оно возрастает.
Вставка требует одного апдейта, чтобы освободить место и раздвинуть номера.