Пишу простое дерево поиска с одной деталью: в каждой вершине

храню размер поддерева этой веришны, структура выглядит вот так:

struct Node {
key: i64,
left_ptr: Option<Box<Node>>,
right_ptr: Option<Box<Node>>,
size: usize,
}

для вставки и удаления написал общую функцию обхода, дело только в том, что для поддержания корректного состояния Node.size в случае если элемент найден/не найден, либо уменьшать значения size у всех предков по пути к искомой вершине, либо не уменьшать - в зависимости от выполнения условия соответственно. для этого надо поддерживать Vec<&mut Option<Box<Node>>>, в который на каждом шаге обхода дерева добавлять ссылку на вершину в конец. В итоге выходит так, что в коде возникает повторный borrowing мутабельных ссылок. Как мне правильно откорректировать решение, чтобы все было правильно?

Не совсем понимаю задачу. Вам надо обновлять size каждой ноды при вставке/удалении из дерева? Вставка/удаление будут делаться через корень дерева, и делаться рекурсией? Тогда не нужна доп ссылка на ноды дерева, можно менять size рекурсивно post order

а вот рекурсивное рабочее решение я написал, хочется не рекурсивное. по идее же как-то можно сымитировать стек, чтобы в нерекурсивном тоже все работало

С этим не подскажу. В си или крестах это решается стеком на хипе с мутабельными ссылками на ноды дерева. В расте такое по идее тоже должно работать (дерево будет владеть нодами, стек - мутаьельно ссылаться)

Рекурсивное работает из-за reborrowing мутабельных ссылок. Для итеративного нужно в одном скоупе держать и мутабельную ссылку на корень и мутабельную ссылку на поддерево - в rust этого сделать нельзя. Или unsafe и указатели или что я выше написал

а зачем на корень держать?

чтобы имитировать стек. На корень и на все остальные по пути до текущей вершины

а когда мы спускаемся по дереву вниз, считается, что все вершины, которые мы прошли, они в статусе borrowed?