Недавно у меня было собеседование на должность, касающуюся чрезвычайно больших распределенных систем, и один из вопросов, которые мне задавали, заключался в том, чтобы создать функцию, которая могла бы полностью подсчитывать узлы в двоичном дереве;что означает отсутствие рекурсии и отсутствие очереди или стека для итеративного подхода.
Я не думаю, что когда-либо видел решение, в котором не использовалось бы хотя бы одно из вышеперечисленного, ни в школе, ни после.
Я упоминал, что наличие «родительского» указателя несколько упрощает проблему, но добавление даже одного простого поля к каждому узлу в дереве с миллионом узлов не является тривиальным с точки зрения стоимости памяти.
Как это можно сделать?