Removing a tree element fails when the element is the tree root's only element, and where the root node has two children each with the minimum # of children.
In the typical case, after merging a node's ith and (i+1)th children, the node's ith element would be moved inside the newly merged ith child.
However, when the root node has 1 element and merges its only children, the root is left with no elements and the newly-merged child is promoted to root.
The code assumed that after a merge, the ith element would be inside the node's ith child. It would not find the element in the very specific case mentioned above, and therefore would not remove it.
The fix is to stop assuming the location of the element after a merge, and instead just recursively call remove on the node.
Removing a tree element fails when the element is the tree root's only element, and where the root node has two children each with the minimum # of children.
In the typical case, after merging a node's ith and (i+1)th children, the node's ith element would be moved inside the newly merged ith child.
However, when the root node has 1 element and merges its only children, the root is left with no elements and the newly-merged child is promoted to root.
The code assumed that after a merge, the ith element would be inside the node's ith child. It would not find the element in the very specific case mentioned above, and therefore would not remove it.
The fix is to stop assuming the location of the element after a merge, and instead just recursively call remove on the node.