Preface
During my interviews at Microsoft's Internet Engineering Institute, two rounds asked about a basic operation on a binary search tree: deleting a node. The first time it came up, I told the interviewer I had read about it but needed time to re-derive it, so he did not press further; but in the second interview, the interviewer insisted that I write code to implement it, so under intense pressure I essentially re-derived it again on the spot. Although what I wrote at the end still had minor flaws, it was also clear that the interviewer could not really understand my implementation either. Later he only asked: if I were testing, how would I test my own code? I roughly said the main points would be boundary tests covering basic BST shapes, branch-condition tests constructed manually based on the code logic, and large-scale tests on randomly built trees.
But this detail left me quite puzzled. It seemed that in the interviewers' view, this is a very basic operation: something you should be able to code without much thinking. Yet in my memory, when working through Introduction to Algorithms, this operation was clearly split into several complicated cases and discussed with strict, detailed care. It is quite tedious to implement; if you have not memorized it deliberately, it is probably hard to write correctly on the spot. So why do interviewers like asking it so much?
After the interview, I spoke privately with a master's student from Tsinghua and only then realized where the issue was: the BST node-deletion algorithm the interviewers had in mind likely came from the simpler algorithm in the first and second editions of Introduction to Algorithms, while the third edition revised it with a more rigorous and detailed treatment. When I studied it, I was looking at this rigorously corrected version, so it felt complex and hard to remember. But for the interviewers, this knowledge point was still based on the older edition, so naturally they did not consider it complicated. Since my AA interview happened to run into a foreign interviewer, that interview was basically already lost; but in any case I learned something useful. Here I summarize and analyze it, hoping I might be able to clear things up for others.
Simple Version
I actually came up with this simplified node-deletion algorithm entirely on my own during the interview, but at the time I thought it was something I had just made up, so I did not dare to write code for it. Only later did I realize that my made-up idea was in fact the correct approach—just a widely known but not-so-rigorous one. Let us first analyze this method.
Given a binary search tree and a key, to delete the node containing that key, we first need to find a pointer z to the node containing the key. Then the node to be deleted falls into the following three cases:
zhas no children, so deletez;zhas one child, still deletez;zhas two children, so deletez's successory.
For the first two cases, regardless of whether z is the left or right child of its parent, we only need to cleanly update the parent pointer of z to point to NULL or to z's child. It is easy to prove that this operation will not break the BST property.
In the third case above, it is clear that z's successor y must lie in z's right subtree, because the precondition already guarantees that z has children. Moreover, we can guarantee that the successor y must belong to one of the first two cases above: it cannot have both left and right children, otherwise it would not satisfy the definition of a successor. Therefore, we only need to swap the key data of z and y, and then delete the node pointed to by y as in the first two cases. It is also easy to prove that this operation will not break the BST property.
Rigorous Version
Consider the implementation of red-black trees in the STL: it includes an erase method that can take the key to be deleted as a parameter, and it can also take a pointer to the node to be deleted. If we analyze the algorithm above more carefully, we will easily discover the problem: if the node to be deleted has both left and right children, then we are not actually deleting the node pointed to by the input pointer; instead, we delete some other node in the BST! In that case, if elsewhere in the program we need to maintain pointers to nodes in the tree, then when we actually use those pointers, they may have mysteriously become invalid. Accessing already-freed memory is obviously a major taboo in C++, and the program can easily crash—this would be a very serious bug.
For this reason, the third edition of Introduction to Algorithms revised this algorithm, adding more complex case discussions for rigor. I will not repeat how the book describes the deletion operation, because it is already sufficiently detailed and rigorous. I only want to further discuss my own understanding.
First, for the first two cases in the “simple version” algorithm, clearly no changes are needed; the handling is exactly the same. The key lies in handling the third case: how to adjust the BST to preserve its properties under the constraint that we must delete the node pointed to by the pointer.
The core idea is still similar: we need to find the successor of the node to be deleted z. The key difficulty is what to do after finding this successor. Here we need to discuss two cases.
Case 1: z's successor is the root of its right subtree
In this case, by the property of successors, z's successor y must have no left child. Then we connect z's left subtree to y's left child, and use y to directly replace z. This clearly satisfies the BST property: all nodes in y's left subtree are smaller than y, meaning the BST property is not violated. y's right subtree is not modified at all, so it also satisfies the BST property. After this operation, we delete only z itself while keeping all other nodes; no information is lost.
Case 2: z's successor is not the root of its right subtree
This case is slightly more complex. Clearly we still need to use z's successor y to replace z, but before that we need extra adjustments to preserve the BST property and not lose any nodes.
First, we replace y with y's right child. This operation is performed with respect to y's parent node, which is equivalent to deleting node y from the BST. By the property of successors, y has no left subtree, so at this point we can consider y's left and right pointers to both be NULL. Next, since node y has been “cleaned up,” we can directly use node y to replace z.
After the operations above, we in fact still keep z's successor node y, and delete z itself. Meanwhile, looking at the whole process, we only performed two replacements. One can prove that both replacements preserve the BST property. The correctness of the first replacement is obvious, so here we only analyze the second: since y is z's successor, it is clear that all keys in z's left subtree are smaller than y; and because y is removed from z's right subtree, all elements in the updated z's right subtree must be greater than y.
In summary, after these case-based operations, the algorithm deletes the node pointed to by the pointer and always preserves the BST property. Therefore the algorithm is correct, and its time complexity is clearly O(h).
Summary
Although in the final interview it was apparent that the interviewer himself did not deeply understand BST deletion—many people, including him, have long treated a non-rigorous algorithm as the correct one—ultimately, situations like this kind of “mix-up” still come down to my own understanding of the algorithm not being deep enough. In future study, I need to practice more and think more, to generalize from one example to others, in order to gain truly thorough understanding.
No matter what the interview outcome is, I must press forward with all my strength. I write this to encourage myself.
Late night, January 23, 2015