Kevin Wampler <wam### [at] uwashingtonedu> wrote:
> 1) Flatten BSTs into sorted arrays / linked lists O(n+m)
> 2) Merge arrays O(n+m)
> 3) Rebuild BST from sorted array O(m+n)

  If there's a way to build a BST from a sorted array on linear time,
you are right. There probably is. It saves the need for rebalancing
after each insertion.

  Since elements in a BST usually have pointers to each other anyways,
and since merging two linked lists can be done without requiring any
additional memory, this whole operation might be possible using O(1)
memory. (Although building a BST from a linked list might require
O(log n) memory.)

-- 
                                                          - Warp

Post a reply to this message