2 ms·
If you're willing to burn O(n) memory on it you could just create an array of pointers to the nodes in the list and then use that to build the balanced tree. I
by jandrese 9y ago
If you're willing to burn O(n) memory on it you could just create an array of pointers to the nodes in the list and then use that to build the balanced tree. It's probably faster than iterating over the sublist every time to find the center.
This assumes of course that the list is sorted. If not, you should probably sort the list first to avoid driving yourself insane.
If memory is too tight to make temporary storage and the list is too big to sort and you want a perfectly balanced tree then you've got an interesting problem on your hands.
- pklausler 9y agoYou can sort a linked list in O(nlog(n)) time with O(log(n)) space, and then convert it to a balanced binary tree in O(nlog(n)) time and O(log(n)) space. EDIT: demonstration: sortList [] = [] sortList [x] = [x] sortList xs = merge (sortList as) (sortList bs) where (as, bs) = split xs split [] = ([], []) split [x] = ([x], []) split (x:y:rest) = let (xs, ys) = split rest in (x:xs, y:ys) merge xs [] = xs merge [] ys = ys merge (x:xs') ys@(y:_) | x <= y = x : merge xs' ys merge xs (y:ys) = y : merge xs ys data Tree a = Empty | Node a (Tree a) (Tree a) deriving(Show) balancedTree xs = mktree (length xs) xs where mktree 0 [] = Empty mktree n xs = Node x (mktree n' less) (mktree (n - 1 - n') more) where n' = (n - 1) `div` 2 (less, (x:more)) = splitAt n' xs listToBalancedTree :: Ord a => [a] -> Tree a listToBalancedTree = balancedTree . sortList