Inserting list into Binary Tree in Haskell

Question

Basically, I'm trying to insert elements from the list into the binary tree one by one, or that's what I thought it should be done when inserting list to the tree.

Here is my tree for inserting:

data Tree = EmptyTree | Node Integer Tree Tree deriving (Show, Eq, Ord)
insertElement x EmptyTree = Node x EmptyTree EmptyTree
insertElement x (Node a left right) = if x == a
                                  then (Node x left right)
                                  else if x < a
                                  then (Node a (insertElement x left) right)
                                  else
                                  Node a left (insertElement x right)

and I thought I could use map to get elements from list and insert it into the list.

Something like this: inserter x = map (insertElement x EmptyTree) where I get list with inserter and insert it into the list.

But, this code is pretty much incorrect I think, and I was wondering how can I do this?

Note that this implementation won't produce a balanced tree and you won't be guaranteed O(log n) lookup. For example, if you convert a sorted list to a tree with this, the depth of the tree will be equal to its length, giving O(n) lookup. — Hjulle
– Hjulle, Commented Apr 21, 2022 at 10:54

willeM_ Van Onsem · Accepted Answer · 2022-04-21 10:32:47Z

4

If you would use inserter xs = map (`insertElement` EmptyTree) you will create a list of trees where each item is inserted once.

What you can do is use foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b or foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b to each time pass the accumulator, the thus far build up list, and thus insert the next item, so:

inserter :: Foldable f => f Integer -> Tree
inserter = foldr insertElement EmptyTree

or:

inserter :: Foldable f => f Integer -> Tree
inserter = foldl (flip insertElement) EmptyTree

It might however make more sense to allow to specify the base tree, and thus using inserter to insert a Foldable of items to a Tree that might already contain items, for example:

inserter :: Foldable f => Tree -> f Integer -> Tree
inserter = foldl (flip insertElement)

answered Apr 21, 2022 at 10:32

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user1348 Over a year ago

Is it also possible with a map? because I'm inserting a value something like this: [1,2,3,4] and I'm not quite familiar with Foldable

willeM_ Van Onsem Over a year ago

@user1348: a list is one of the foldables, so can use a list, a Maybe , etc.

chi Over a year ago

@user1348 Use map when you want to convert a list-of-A to list-of-B. If you want the result to be a tree, and not a list, map is the wrong tool. Use a fold (left or right) instead.

chepner Over a year ago

map encapsulates a particular pattern of recursion that is different from the pattern you want.

Collectives™ on Stack Overflow

Inserting list into Binary Tree in Haskell

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related