Any way to do a binary tree traversal without `opApply` and allocations?

[solidstate1991]

On Thursday, 26 March 2026 at 21:47:59 UTC, solidstate1991 wrote:
> Thanks to DMD 2.112.0, my library `collections-d` is now 
> broken, any attempt at fixing it is futile thanks to `@system` 
> functions being able to call `@safe` functions, so the compiler 
> is immediately crashing out the moment there's an `@system` 
> level function. I had to completely ditch the `@trusted` ones
>
> Is there some other way to implement a tree traversal, that 
> preferably works with `foreach` or at least somewhat easy to 
> use? I often have to rely on binary trees, both in garbage 
> collected threads and low-level/low-latency ones, in the latter 
> "just let the GC do its thing!" does not work well. "Building 
> an array from the tree" (as some suggested) also not really a 
> good idea, given that I'd have to constantly allocate a new 
> array. Adding a root pointer to each node is not ideal either, 
> but might be a less bad idea, than letting go of low-latency 
> threads.
>
> BTW, due to the whole attribute hell issue, every time I need a 
> collection, I have to do something like this, just to make sure 
> I don't have every foreach loop as `@system`, impure, 
> potentially throwing, and GC allocating regardless of the 
> content of the foreach loop:
>
> ```d
> string makeFunc(string attr) {
> 	import std.array : replace;
> 	return replace(q"{
> 		int opApply(scope int delegate(ref E) #attr dg) #attr {
> 			if(left !is null)
> 				if(int r = left.opApply(dg))
> 					return r;
> 			if(int r = dg(elem))
> 				return r;
> 			if(right !is null)
> 				if(int r = right.opApply(dg))
> 					return r;
> 			return 0;
> 		}
> 		int opApply(scope int delegate(K, ref E) #attr dg) #attr {
> 			if(left !is null)
> 				if(int r = left.opApply(dg))
> 					return r;
> 			if(int r = dg(key, elem))
> 				return r;
> 			if(right !is null)
> 				if(int r = right.opApply(dg))
> 					return r;
> 			return 0;
> 		}
> 		int opApplyReverse(scope int delegate(ref E) #attr dg) #attr {
> 			if(right !is null)
> 				if(int r = right.opApplyReverse(dg))
> 					return r;
> 			if(int r = dg(elem))
> 				return r;
> 			if(left !is null)
> 				if(int r = left.opApplyReverse(dg))
> 					return r;
> 			return 0;
> 		}
> 		int opApplyReverse(scope int delegate(K, ref E) #attr dg) 
> #attr {
> 			if(right !is null)
> 				if(int r = right.opApplyReverse(dg))
> 					return r;
> 			if(int r = dg(key, elem))
> 				return r;
> 			if(left !is null)
> 				if(int r = left.opApplyReverse(dg))
> 					return r;
> 			return 0;
> 		}
> 		}", "#attr", attr);
> }
> ```
>
> This is then used in a `mixin` to generate the required 
> overloads, where `attr` means the attributes I need for the 
> overload.
>
> Someone really needs to write a DIP for it...

Was about to move to the `front`, `popFront`, and `empty` trio, 
but then I remembered it doesn't support keys...