As a challenge, a colleague of mine told me to find a non-recursive constant-space algorithm for deleting a binary tree.¹
After a moment’s thought, I was able to come up with an algorithm. It is often the case that solving a problem is easier once you are told that a solution exists.
When I asked the Internet for a non-recursive constant-space algorithm, it seems that everybody uses an algorithm different from the one I found, so let’s look at that one first.
The idea behind that algorithm is to start with the algorithm for iteratively traversing a binary tree in which each node also remembers its parent. The linked article does an inorder walk, so we’ll adapt the N-ary postorder walk.
struct Node
{
Node* left;
Node* right;
Node* parent;
Data d;
};
void DeleteTree(Node* node)
{
while (node) {
// Go left as far as you can.
while (node->left) {
node = node->left;
}
// If you can't go left, try going right one step,
// and then continue the leftward descent.
if (node->right) {
node = node->right;
continue;
}
// At the bottom. Delete the node and head back up.
while (node) {
auto parent = node->parent;
delete node;
if (!parent) {
return; // all done
}
// If we came from the left child,
// then go to the right child if there is one.
if (node == parent->left && parent->right) {
node = parent->right;
break;
} else {
// No more children, so keep walking up.
node = parent;
}
}
}
}
The only tricky part is that our N-ary postorder walk wants a NextSibling, but we don’t have that. We synthesize it by realizing that in a binary tree, each parent has only two children, so if you are a child, you are either the left child (in which case the next sibling is the right child, if you have one) or the right child (in which case there is no next sibling). You can figure out which one you are by seeing if you are your parent’s left child.
Next time, we’ll figure out where to get the parent pointer when we don’t have one.
¹ You might be in need of such an algorithm if your tree can get very deep, so a recursive algorithm would exceed available stack space. The constant space requirement is important because this ensures that you don’t run into a low-memory error when trying to free up memory. C++ destructors are noexcept by default, and even if you mark them as potentially-throwing, throwing an exception from a destructor that is called due to unwinding is considered a fatal error that results in immediate termination of the program. Clean-up functions cannot fail.
The more constrained the problem, the simpler it is to solve.
In the extreme, if you are decommissioning the hardware, you can just yank the plug, but that doesn’t make for an interesting blog post. (Though I do know of some systems where the process shutdown explicitly assumes that all programs will end with a crash and that no destruction will happen on the way down. Makes thing fast and forced you to deal with a lot of abnormal cases by making them be the normal case.)
auto parent = node->parent; delete node; if (!parent) { return; // all done } // ... if (node == parent->left && parent->right) {This code has undefined behavior. You’re not allowed to compare pointers to dead objects, so you need to do the comparison first:
auto parent = node->parent; if (!parent) { delete node; return; // all done } auto was_left_child = node == parent->left; delete node; // ... if (was_left_child && parent->right) {That undefined code will work just fine in any sane compiler (i.e. all of them). In the wise words of Linus Torvalds, when the standard is bogus garbage, it needs to be explicitly ignored, and it needs per-compiler workarounds for braindamage.
Linus Torvalds and his army of yes-men have done a tremendous amount of damage to discourse around sane language design.