Если сразу при удалении узла, например, левого потомка для родителя (кейс с удалением узла с именем 3), возвращать родителю флаг иметь левого потомка в true, то начинает некорректно отрабатывать добавление узла 16. В этом случае 16 добавляется под 1, а не под 9, как на рисунке. Но валидатор это пропускает! Если при удалении потомков для родителя не восстанавливать флаги возможности добавить потомков в true, то после удаления вершин 3, 4, 5, 6 остаётся обрубок дерева с вершинами 1 и 2, которые содержат флаги возможности добавления лотомков со значениями false. И по логике последнего условия требуется их переключить в true. Но это какой-то костыль. И даже если это сделать при размере дерева меньшем или равным 2, то валидатор всё равно хочет явно чего-то другого. Что хотел сказать автор задачи я так и не понял. Восстанавливаю возможности отрастить потомка сразу после его удаления и забил на кейс с добавлением 16 не на своё место.