educative.io

Educative

Why not two binary search trees?

Hey all!

I was thinking through this problem. The solution I would have come up with would have been similar, but to use two balanced binary search trees instead of heaps (similar to a Java SortedSet or something). This seems to give an overall runtime of O(n log k) which might be slightly improved over the two heaps solution.

At each step, we effectively do the same thing, expect for the max and min now take O(log k) and the linear search for the node to be removed is swapped for the tree lookup at O(log k).

I was wondering if anyone had any thoughts about solving this problem in this way.

1 Like

Hi @Leland_Miller,

Yeah, it makes sense. However, as you can see that the name of the chapter is Pattern: Two Heaps, so we are bound to use heaps in the solution.

I guess the current example could use Binary Search Tree, the Time Complexity of finding the biggest or smallest value in the Binary Search Tree is O(log(n)), whilst using Heap is O(1) in the last example.