Build balanced binary tree with foldr

Question

I write the function foldTree that build balanced binary tree from list. I must use foldr and it's ok, i used it, but i make insertInTree function recursive =( for now i know only this way to walk through the trees =)).

UPDATE: iam not sure about function insertTree: is it right calculate the heights in recursion?? =(( need some help here.

Is it possible to write insertInTree without recursion (something with until/iterate/unfoldr) or make foldTree function without helper functions => shorter somehow?

this is my try below:

data Tree a = Leaf
            | Node Integer (Tree a) a (Tree a)
            deriving (Show, Eq)

foldTree :: [a] -> Tree a
foldTree = foldr (\x tree -> insertInTree x tree) Leaf

insertInTree :: a -> Tree a -> Tree a
insertInTree x Leaf = Node 0 (Leaf) x (Leaf)
insertInTree x (Node n t1 val t2) = if h1 < h2 
                                    then Node (h2+1) (insertInTree x t1) val t2 
                                    else Node (h1+1) t1 val (insertInTree x t2) 
  where h1 = heightTree t1
        h2 = heightTree t2

heightTree :: Tree a -> Integer
heightTree Leaf = 0
heightTree (Node n t1 val t2) = n

output:

*Main> foldTree "ABCDEFGHIJ"
Node 3 (Node 2 (Node 0 Leaf 'B' Leaf) 'G' (Node 1 Leaf 'F' (Node 0 Leaf 'C' Leaf))) 'J' (Node 2 (Node 1 Leaf 'D' (Node 0 Leaf 'A' Leaf)) 'I' (Node 1 Leaf 'H' (Node 0 Leaf 'E' Leaf)))
*Main> 

Answer 1

Your insertion function is in error when the two sub-trees' heights are equal, because inserting into the right sub-tree will increase its height if it was already full. It is not immediately clear to me whether such situation will ever arise or not in your code.

The apparently correct way to insert a new element into a tree seems to be

insertInTree x (Node n t1 val t2) 
    | h1 < h2   = Node  n (insertInTree x t1) val t2 
    | h1 > h2   = Node  n    t1 val t2n 
    | otherwise = Node (h+1) t1 val t2n  
  where h1  = heightTree t1
        h2  = heightTree t2
        t2n = insertInTree x t2
        h   = heightTree t2n     -- might stay the same

This creates almost balanced trees (a.k.a. AVL-trees). But it pushes each new element to the very bottom of the tree.

edit: These trees can be nicely seen with

showTree Leaf = ""  
showTree n@(Node i _ _ _) = go i n
  where
  go _ (Leaf) = "" 
  go i (Node _ l c r) = go (i-1) l ++ 
    replicate (4*fromIntegral i) ' ' ++ show c ++ "\n" ++ go (i-1) r 

Try

putStr . showTree $ foldTree "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"

And yes, you can write foldTree shorter, as

foldTree = foldr insertInTree Leaf

Answer 2

Just want to point out that the accepted answer is good but will not work after having a height 3 balanced binary tree as it did not consider the fact that the left tree could have less height than the right after inserting.

Apparently, the code could've worked adding an extra condition:

insertInTree x (Node n t1 val t2) 
    | h1 < h2   = Node  n      t1n val t2 
    | h1 > h2   = Node  n      t1  val t2n
    | nh1 < nh2 = Node  n      t1n val t2
    | otherwise = Node (nh2+1) t1  val t2n 
  where h1  = heightTree t1
        h2  = heightTree t2
        t1n = insertInTree x t1
        t2n = insertInTree x t2
        nh1 = heightTree t1n
        nh2 = heightTree t2n