# If a Tree Falls in a Forest, Does It Overflow the Stack?Nov 18, 2022

A well-known pitfall when implementing a linked list in Rust is that the the default recursive `drop` implementation causes stack overflow for long lists. A similar problem exists for tree data structures as well. This post describes a couple of possible solutions for trees. This is a rather esoteric problem, so the article is denser than is appropriate for a tutorial.

Lets start with our beloved linked list:

Its easy to cause this code to crash:

The crash happens in the automatically generated recursive `drop` function. The fix is to write `drop` manually, in a non-recursive way:

What about trees?

If the tree is guaranteed to be balanced, the automatically generated drop is actually fine, because the height of the tree will be logarithmic. If the tree is unbalanced though, the same stack overflow might happen.

Lets write an iterative `Drop` to fix this. The problem though is that the swap with `self` trick we used for list doesnt work, as we have two children to recur into. The standard solution would be to replace a stack with an explicit vector of work times:

This works, but also makes my internal C programmer scream: we allocate a vector to free memory! Can we do better?

One approach would be to build on balanced trees observation. If we recur into the shorter branch, and iteratively drop the longer one, we should be fine:

This requires maintaining the depths though. Can we make do without? My C instinct (not that I wrote any substantial amount of C though) would be to go down the tree, and stash the parent links into the nodes themselves. And we actually can do something like that:

• If the current node has only a single child, we can descend into the node
• If there are two children, we can rotate the tree. If we always rotate into a single direction, eventually well get into the single-child situation.

Heres how a single rotation could look:

Or, in code,

Ok, what if we have an n-ary tree?

I think the same approach works: we can treat the first child as `left`, and the last child as `right`, and do essentially the same rotations. Though, we will rotate in other direction (as removing the right child is cheaper), and well also check that we have at least two grandchildren (to avoid allocation when pushing to an empty vector).

Which gives something like this:

I am not sure this works, and I am not sure this works in linear time, but I am fairly certain that something like this could be made to work if need be.

Though, practically, if something like this is a concern, you probably want to re-design the tree structure to be something like this instead:

Update(2023-11-03): Apparently, dropping trees iteratively was trendy in Dec. 2022! The same idea was described by Ismail in this great post:

https://ismailmaj.github.io/destructing-trees-safely-and-cheaply