If a Tree Falls in a Forest, Does It Overflow the Stack?
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.
Let’s start with our beloved linked list:
It’s easy to cause this code to crash:
The crash happens in the automatically generated recursive
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.
Let’s write an iterative
Drop to fix this.
The problem though is that the “swap with
self” trick we used for list doesn’t 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 we’ll get into the single-child situation.
Here’s 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 we’ll 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: