Задача. Полное бинарное дерево

Дан корень бинарного дерева. Необходимо определить, является ли оно полным бинарным деревом?!

Справка: Полное бинарное дерево — это бинарное дерево, в котором все уровни, кроме, возможно, последнего, полностью заполнены, а все узлы последнего уровня максимально левые.

Примеры:

1. Полное бинарное дерево

2. Не полное бинарное дерево

Разбор

По сути, будем использовать определение полного бинарного дерева. Сделаем обход бинарного дерева по уровням (pre-order traversal) и если мы встретим пропущенный узел, после которого есть заполненные, то такое дерево будет неполным.

Для обхода дерева воспользуемся очередью:

1. В 1-м цикле мы последовательно запишем все ненулевые узлы, поочередно обходя каждый уровень.
2. Во 2-м цикле мы проверим все ли оставшиеся узлы в очереди являются нулевыми. В полном дереве это будут нулевые дочерние узлы последнего уровня. В этом цикле каждый элемент мы удалим из очереди.
3. Если очередь оказалась пустой, то дерево полное.

Реализация

Play-test

https://dotnetfiddle.net/8xddeV