The search-tree invariant is not a rule about a node and its two children; it is a rule about whole subtrees, and a tree can satisfy the local version and violate the real one. The lab draws that tree. Deleting a node with two children is the one operation with a case to remember: replace it by its in-order successor, which has at most one child.
Core ideas
The definition, the one delicate operation, and the check people substitute for the definition without noticing that it is weaker.
At every node, every key in the left subtree is smaller and every key in the right subtree is larger. That is what lets a search discard half the remaining tree at each step on the strength of one comparison: if the target is smaller than this node it cannot be anywhere to the right, because nothing to the right is smaller. A local rule about two children would not license that.
Checking only that each node is larger than its left child and smaller than its right child passes on the tree with root 20, left child 10, and 25 hanging as the right child of 10. Every parent-child pair is in order. But 25 is in 20’s left subtree and 25 > 20, so a search for 25 turns left at the root and never finds it.
A node with no children or one child is unlinked. A node with two children cannot be: both subtrees have to stay attached to something in the right order. The key that can take its place is its in-order successor — the smallest key in its right subtree — and that node has no left child by construction, so removing it is the easy case.
The material
Why search is one path, what the local check misses, and the successor substitution done by hand.
A binary tree in which, at every node x, every key in the left subtree of x is less than the key at x, and every key in the right subtree of x is greater than it. Duplicate keys are excluded here.
The condition is quantified over subtrees, not over children. That is the whole of the definition and the source of the only misconception in this lesson.
Search follows one path. Compare the target with the root: equal and you are done; smaller and the target can only be in the left subtree, because every key to the right is larger; larger and only in the right. Repeat. The number of comparisons is one per level visited, so at most the height plus one. Insertion is the same walk, ending at the empty position where the search failed.
Traverse left subtree, then node, then right subtree, recursively. The sequence of keys produced is in increasing order if and only if the tree is a binary search tree.
One direction is the invariant unrolled: everything in the left subtree is smaller than the node and is emitted before it, and everything in the right subtree is larger and is emitted after. The other direction is why this is useful as a test — a walk that comes out sorted certifies the invariant everywhere, including the subtree conditions the local check never looks at.
Root 20, left child 10, right child 30, and 25 as the right child of 10. Local check: 10 < 20, 30 > 20, 25 > 10. All pass. In-order walk: 10, 25, 20, 30 — not sorted, and the walk names the offender. The lab builds this tree and evaluates both checks on it in your browser, reporting the local one as satisfied and the real one as violated.
No children: unlink it. One child: splice the child into its place, which preserves the invariant because the whole subtree moves up unchanged and its keys were already on the correct side of everything above. Two children: neither child can simply take the node’s place, because the other subtree would have nowhere correct to go.
So replace the key rather than the node. The in-order successor is the smallest key in the right subtree — walk right once, then left as far as possible. Every key in the left subtree is smaller than it (they were smaller than the node, which is smaller than everything right), and every remaining key in the right subtree is larger than it (it was the smallest). So it can sit where the deleted node was. And it has no left child, or it would not have been the smallest, so removing it from where it was is one of the two easy cases.
The lab counts 13 comparisons for those eight operations and reports the resulting height as 2. Deleting the root instead of 30 is the same rule with a longer reach: the successor of 50 is 60, which lives in the other subtree, and 60 becomes the root while 70 keeps 80 as its right child. The tree is different and the in-order sequence is still sorted, which is the only thing the invariant asks.
Search for 40 in the seven-key tree before that deletion and the lab reports the path 50 → 30 → 40: three comparisons, and the panel prints the route so the path is a thing you can see rather than infer. Search for 55 and it reports three comparisons and not found. Run the same eight operations with the keys arriving as 20, 30, 40, 50, 60, 70, 80 and the seven insertions build a path of height 6, the whole sequence costs 23 comparisons rather than 13, and the delete leaves a tree of height 5.
That last pair is the warning. The invariant says nothing about the shape, so it says nothing about the cost: 13 comparisons and 23 comparisons come from the same keys and the same algorithm, and the only difference is the order they arrived in. A search tree is O(log n) per operation exactly when it is short, and nothing established so far makes it short. The next lesson is about what does.
Interactive
Delete a node with two children and watch its successor move up
Method
Four steps, and the fourth is the one that catches a broken tree that looks fine.
Smaller, go left; larger, go right; equal, stop. Write the path down. The comparison count is the path length, and a path longer than about log₂ n is telling you something about the shape rather than about the search.
Run the search for the new key. It ends at an empty child pointer, and that is the only place the key can go without breaking the invariant. There is no choice to make, which is exactly why the insertion order determines the shape.
Zero or one child: unlink or splice. Two children: find the in-order successor — right once, then left until you cannot — move its key up, and delete it from where it was. Saying which case you are in before acting is what keeps the two-child case from being attempted as a splice.
Emit left, node, right. If the sequence is sorted the invariant holds everywhere; if it is not, the first out-of-order pair names the offending key. Checking each node against its two children can pass on a tree that is not a search tree, and the lab has that tree.
The lab’s opening sequence with the comparison counter shown. The last line is the deletion the lesson is about.
The successor of 30 was 40, one step to the right and then no left child to follow. That is the common case and it makes the operation look trivial. Delete 50 from the original tree instead and the successor is 60, reached by going right to 70 and then left once — and 60 becomes the root of the whole tree while 70 keeps 80. Same rule, longer walk.
Count the comparisons and then count them again for the same seven keys arriving as 20, 30, 40, 50, 60, 70, 80. The seven insertions build a single path of height 6, the eight operations cost 23 rather than 13, and every search is a scan. Nothing in the invariant was violated. The cost changed because the shape changed, and the shape was decided by the arrival order.
For a faded rehearsal, build 50 30 70 20 40 60 80 and then delete 70. The supplied first move is that 70 has two children, so the successor is the smallest key in the subtree rooted at 80 — which is 80 itself, since it has no left child. Carry out the substitution, write the in-order walk, and confirm it is still sorted. Then run the local check on the lab’s counterexample tree and say, in one sentence, what the walk detects that the local check cannot.
You should be able to search, insert and delete by hand including the two-child case with the successor named, produce the in-order walk of a drawn tree, explain why the local check is weaker using the four-node counterexample, and state plainly that the invariant bounds nothing about the height.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.