On 1/31/2012 1:23 AM, Invisible wrote:
> Question: If you have a bunch of data in sorted order, how do you build
> a BST from that faster than O(n log n) times?
>
> (I can kind of see how that would work if the data is in an array;
> arrays support random access, so you could just binary chop the array
> and keep the results as a BST. I'm trying to figure out if you can do
> anything with a linked list, which does /not/ support random access...)

Although I haven't done it myself, I believe if you actually do the 
complexity analysis you'll find that the lack of random access doesn't 
change the complexity of the obvious recursive algorithm except by a 
constant factor.

Post a reply to this message