Итерации удалить узел и его потомков в бинарном дереве

Question

Example Tree image

Учитывая бинарное дерево и указатель на узел (который присутствует) в дереве, предположим, что у нас есть родительские указатели. Мне нужно найти количество итераций для удаления соседних узлов и последующих соседних узлов этих удаленных узлов. Здесь удаление означает установку некоторого флага, узла -> запись. Я не удалю узел. Пример:

  1 
    / \ 
     2  3 
    /\ /\ 
    4 5 6 7 
//
    8 9 
/
10 

и данный узел в дереве равно 4,

Сгоревшие узлы в каждой итерации

В итерации 1:

• Для узла 4: 4,8, 2 (8 - дочерний узел, 2 - родительский элемент 4, это соседние узлы 4).

В итерации 2:

• Для узла 8: 10 будет сожжено. (4 уже сожжено)
• Для узла 2: 5 и 1 будет сожжен.

Это продолжается ... поэтому я должен найти количество итераций, необходимых для записи всех узлов.

Answer 1

не эффективен, но я думаю, что это будет работать:

Поддерживайте очередь для следующих узлов, которые будут рассматриваться для удаления. И перед удалением соседних узлов узла проверьте, установлены ли они уже установленным флагом burn.

Кроме того, каждый раз, когда вы удалить элемент из очереди:

• проверить, если все узлы сжигаются или нет (для этого вы можете поддерживать Hash для быстрого доступа)
• приращение счетчика итераций (что будет вашим результатом)