[Haskell-cafe] inserting values in a binary tree

Bulat Ziganshin bulat.ziganshin at gmail.com
Fri May 9 19:27:17 EDT 2008

Hello PR,

Saturday, May 10, 2008, 3:10:59 AM, you wrote:

> in C you'd fiddle with pointers and Bob's your uncle. Here I'm not
> sure how to piece that tree back together again with the new element 
> after having expanded it recursively.

in Haskell, you just return new tree with element inserted. it's
constructed from the two subtrees, where you've inserted element in
one of these. and so on recursively:

data Tree a = Tree a (Tree a) (Tree a)
            | EmptyTree
insert (Tree x t1 t2) y | x<y  =  Tree x t1 (insert t2 y)
insert (Tree x t1 t2) y        =  Tree x (insert t1 y) t2
insert EmptyTree      y        =  Tree y EmptyTree EmptyTree

Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com

More information about the Haskell-Cafe mailing list