aetilley
commented
1 year ago This perplexed me too.
One solution is to let the binary tree order be not simply ordering on lower endpoint of the interval, but lexicographic ordering on (lower, upper) endpoints (ie. order by lower then upper in case of ties). I think this is what the authors mean by "modifications to the interval-tree procedures".
The current solution is broken if the low endpoints of intervals aren't distinct, in which case we need to recursively call both x.left and x.right as i.high can be in either of the two subtrees. That, I think, is exactly why the exercise asks to "Suggest modifications to the interval-tree procedures", not just "modify Interval-Search". However, I couldn't come up with a solution myself, nor did I find any solution online, so I thought it best to just leave an issue here.