We’ve been looking at non-recursive algorithms for deleting the nodes of a binary tree. The previous algorithm performed a postorder traversal, cleverly repurposing the left link as a parent link once the left child pointer is no longer needed.
As I noted at the start of the discussion, the algorithm I came up with was quite different.
For ease of diagramming, let’s draw the binary tree rotated counter-clockwise 45 degrees, so that the root node in the northwest corner, with left nodes going down the page and right nodes going to the right. I focused on the two pieces coming from the root node: The long left (down) chain and as the right child.
| A | → | 🌳 |
| ↓ | ||
| B | → | … |
| ↓ | ||
| C | → | … |
| ↓ | ||
| â‹® | ||
| ↓ | ||
| Z | → | … |
Before I can delete the root node, I have to arrange for the left and subtrees to be cleaned up eventually. My strategy is first to take the right subtree and graft it onto the end of the leftmost chain:
| A | ||
| ↓ | ||
| B | → | … |
| ↓ | ||
| C | → | … |
| ↓ | ||
| â‹® | ||
| ↓ | ||
| Z | → | … |
| ↓ | ||
| 🌳 |
At this point, the root node has only one child, namely the left child. So I can delete the root node and treat the left child as the new root of what remains.
| A | 🔥 | |
| B | → | … |
| ↓ | ||
| C | → | … |
| ↓ | ||
| â‹® | ||
| ↓ | ||
| Z | → | … |
| ↓ | ||
| 🌳 | ||
I have now reduced the problem to a smaller problem: The new tree rooted at B has one fewer node than the one I started with, so I can repeat the process until all the nodes are deleted.
void DeleteTree(Node* node)
{
// Empty tree: Nothing to do
if (!node) return;
// Find the leftmost node.
Node* last = node;
while (last->left) {
last = last->left;
}
while (node)
{
// Make the right subtree the left subtree
// of the leftmost node.
last->left = node->right;
// Find the new leftmost node.
while (last->left) {
last = last->left;
}
// We have arranged for the eventual
// deletion of all the children. Now we can
// delete the root node and promote the left
// child to be the new root.
delete std::exchange(node, node->left);
}
}
I like this algorithm because it is shorter and much easier to get correct. The order of element destruction is preorder-ish: Every parent is destroyed before its children, and every left child is destroyed before its right sibling. However, the right subtree is not destroyed immediately after the left subtree, so it’s not a true preorder. You can think of it as a topological order.
The running time of this algorithm is O(n) because each node is deleted once, each right link is traversed once (to graft it to the bottom), and each left link is traversed twice (once to find the leftmost node and once when it becomes the root element and is detached from the rest of the tree prior to being deleted).
Bonus chatter: Note that the right thing happens if the root has no right child: A null tree gets grafted to the end of the leftmost node (which has no effect).
Hello I have a question about a Windows 9x Feature.
In the shutdown dialog, when selecting Restart pressing SHIFT and OK, Windows does a fast restart: it prints Windows is now restarting... instead of cold-rebooting the computer.
What exactly happens under the hood? What devices, modules or processes are being involved?
Fun stuff: Winstart.bat gets executed, when KRNL386.EXE is executed directly, it will continue booting Windows to desktop. Then when fast-restarting again it will go back to the command prompt that executed KRNL386.EXE, however Windows is broken at this point: exiting will cause a Windows Protection Error and executing KRNL386.EXE again will cause...
You could save some of the left link 2nd traversals by doing a "drive-by" grafting/deletion on the way down looking for the leftmost node, say like this:
<code>
One of the other answers on the Code Golf Stack Exchange page linked yesterday seems to resemble this.
https://codegolf.stackexchange.com/a/668