Benchmarks

benches/variants.rs measures the variants with Criterion on a wide tree (10 000 paths of depth 6) and a deep one (one path of depth 1 000), inserting and writing. Writing goes to io::sink(), so that the traversal is measured and not the console; each insert builds one tree, dropped outside the timing.

cargo bench --bench variants

The report is written to target/criterion/report/index.html.

Benchmark	Variant	Median of the means	Means of the runs	Against recursive
insert wide	recursive	8.22 ms	8.22 ms, 8.27 ms, 7.95 ms	—
insert wide	iterative	5.62 ms	6.25 ms, 5.54 ms, 5.62 ms	-32 %
insert wide	explicit stack	5.85 ms	5.78 ms, 5.85 ms, 5.86 ms	-29 %
insert deep	recursive	62 µs	60 µs, 62 µs, 62 µs	—
insert deep	iterative	54 µs	54 µs, 56 µs, 54 µs	-12 %
insert deep	explicit stack	58 µs	59 µs, 57 µs, 58 µs	-6 %
write wide	recursive	3.21 ms	3.41 ms, 3.21 ms, 2.88 ms	—
write wide	iterative	3.30 ms	3.29 ms, 3.30 ms, 3.31 ms	+3 %
write wide	safe	2.97 ms	3.06 ms, 2.97 ms, 2.85 ms	-7 %
write deep	recursive	56 µs	56 µs, 57 µs, 55 µs	—
write deep	iterative	60 µs	60 µs, 61 µs, 59 µs	+7 %
write deep	safe	58 µs	56 µs, 58 µs, 65 µs	+4 %

Measured on an Intel Core i7-7700K under WSL2 (Ubuntu 24.04), rustc 1.98.1, Criterion 0.5: each run pinned to one core (taskset -c 3), 10 s per benchmark, three runs. The table gives the median of the three means, the mean of each run, and the median against the recursive variant.

What the numbers say:

The depth limit costs nothing measurable. safe against recursive: -7 % on the wide tree, +4 % on the deep one - inside a spread of up to ±10 % between runs of the same code. On this machine, differences below about 10 % cannot be told apart.
Writing with an explicit stack costs a little. The stack of iterators is 3 to 7 % slower than the recursion; on the deep tree with the same sign in every run.
Inserting is dominated by allocation, not by the call stack. Every new key allocates a String and a map node. Within a group, the variant measured first is the slowest: in the table that is the recursive one. Measured alone, each in a process of its own and alternating, the three variants lie within about 10 % of each other on the wide tree - iterative 7.6 and 7.0 ms, recursive 8.5 and 7.6 ms, explicit stack 6.9 and 6.8 ms - with overlapping confidence intervals. The order of the measurements and the state of the allocator move the result more than the form of the code.
A benchmark can mislead by itself. A first version collected many trees and dropped them together (iter_with_large_drop); from one run to the next the order of the variants turned over - recursive 15.0 ms against iterative 6.2 ms, then 5.6 ms against 16.4 ms. Each tree is now dropped alone, outside the timing.
The spread is part of the result. A desktop under WSL2 shares its cores with a virtual machine and everything else that runs, and a benchmark that allocates several MB per iteration measures the allocator too. A quiet native Linux machine with a fixed CPU frequency narrows the spread; the conclusions above should hold there, the absolute numbers will not.

The Criterion report of this run - from a shared GitHub runner, indicative only; the numbers above come from a dedicated machine.