current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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
share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.