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) {Technically its not undefined behavior, but rather implementation defined behavior.
i.e. the implementation / compiler must document what happens for that case and apply that behavior consistently.
(in comparison to UB, where the compiler is free to do whatever it pleases)
For example converting pointers to integers is also implementation defined behavior.
The only things you are never allowed to do with invalid pointer values are indirect through them or call a deallocation function with them - those two are UB.
Everything else involving invalid pointer values is implementation defined behavior. (copying them, comparing them, passing them as a parameter to a...
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.
My immediate thought before reading the post was, not assuming the data structure had built-in parent pointers, that it would be easy enough to walk from the root again after each deletion. Definitely inefficient, but similar to a bubble sort in that every step makes progress, the data structure remains consistent even if interrupted partway through, and it can pick up where it left off even if the tree was arbitrarily mutated between calls.
Then I re-read the post title and saw the mention of parent pointers. Yeah, that'd allow for a far more efficient traversal. I think my brain just...
Maybe the code can be simpler by tossing some of the “At the bottom” lines i.e.
... // At the bottom. Delete the node and head back up. auto parent = node->parent; delete node; if (parent) { // Need to erase parent's memory of us if (node == parent->left) { parent->left = nullptr; } else { parent->right = nullptr; } } // Step up node = parent; } }Hmmm … it seems wasteful and possibly incompatible with existing structures to have the parent pointer inside the node. A “trail” (vector) of parents would need to be only as long as the tree depth, and I wonder if it could be further optimized to a single pointer by using XOR tricks between itself and the current node.
This “trail of parents” vector sounds like a stack to me, so your algorithm would still be recursive, even if its stack is not the system one.
@BCS: That’s good for a destruction which is the current scenario, but would be harder to adapt for a regular traversal.
This looks like Deutsch-Schorr-Waite algorithm (https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf).
My first thought on this was that it would be simpler to track where you are in thing if you null out the pointers on the way down. Then the action to use processing a node is the same regardless of how you got there. But if you accept that willingness to muck with the pointer (and temporary break the tree invariants) you could also just set the left child as the parent just before you walk into it and set the right as null before it. Then when you step back up, you just find the next step...