Create Binary, Balanced Tree Attempt #2

Question

Previously, I posted an incorrect implementation of making a binary, balanced tree from a list of a's.

Here's my second implementation:

data Tree a = Leaf
 | Node Integer (Tree a) a (Tree a) 
 deriving (Show, Eq)-- where Integer is the height (bottom = 0)
-- make balanced, binary tree (height diff is 1 at most)
foldTree :: [a] -> Tree a
foldTree [] = Leaf
foldTree xxs@(x:xs) = Node level (foldTree first) x (foldTree rest)
 where (first, rest) = splitInHalf xs 
 level = getBinTreeHt xxs
splitInHalf :: [a] -> ([a], [a])
splitInHalf xs = splitAt mid xs
 where mid = length xs `div` 2
-- Get the total height of a tree given a list of [a] to create a Tree
getBinTreeHt :: [a] -> Integer
getBinTreeHt = floor . (logBase 2) . fromIntegral . length 

Testing

Note that prettyTree's implementation is excluded from this question since it's a library for visually representing a tree. Credit to this answer for prettyTree.

*Main> (putStrLn . prettyTree . foldTree) [0..15]
 15
 14
 12
 13
 8
 11
 9
 10
0
 7
 5
 6
 1
 4
 2
 3

Answer 1

I'd suggest:

• If you have the height of a node in the Node constructor, you don't need to create a separate function getBinTreeHt. It is error prone (what if you change the way the tree is constructed, or add another one?) and costly - each call to it is O(n). Instead, use smart constructors as shown in this answer. Then you'll get the heights computed automatically, with minimal overhead, and it will work correctly regardless of what kind of tree or how you'll be constructing it.
• The implementation is now correct, but it is somewhat inefficient. Since you call splitInHalf for every Node you're constructing, the total time complexity will be O(n^2), as each this call computes length xs and splitAt mid xs, which are both O(n). There is no simple way how to fix that though, you'd need to re-thing the algorithm. (Hints: compute the length only at the beginning and then use it to compute the sizes of subtrees; try to consume the list from the beginning, without splitting, and pass around the unconsumed part, as you're building the tree; if you want, I can provide a code sample.)
• Usually the main reason why you want to have a balanced tree is that you can search in it fast. In order to do that, you need the tree to have the property that all elements in the left (right) subtree of a node are less (greater) than the node's element. I don't know if this is your aim, but if it is, you probably want to modify the algorithm so that if it's given a sorted list, it'll create a balanced, properly ordered tree.