Binary Search Tree Functions in Haskell

Question

I need help in 3 tasks. I'm really new in Haskell and functional programming.

data Tree = Node Int Tree Tree | Nil

Define with help of the function collapse
```
collapse :: Tree -> [Int]
collapse Nil = []
collapse (Node x y z) = (collapse y) ++ [x] ++ (collapse z)
```
a Haskell-Function check :: Tree -> Bool which checks if the Tree is a binary search tree.
I test that with a tree and get 2 4 7 8 10 | 5 6 10 12. Here you can see that all values to the middle are sorted, but I don't know how i should code that.
Define a Haskell-Function insert :: Int -> Tree -> Tree which adds the Integer Value to the Tree and return also a binary search tree.
Define with the function insert (2) a Haskell-Function merge :: Tree -> Tree -> Tree which merges two trees to another binary search tree.

collapse is an in-order traversal. What property of in-order traversals of binary trees characterises binary search trees? — Daniel Fischer
The left node value (int) of an Binary Tree is smaller than the parent node and the right node value is bigger than the parent node and that for each children node. — Chryb
A binary tree is a binary search tree if and only if its in-order traversal is ...? — Daniel Fischer

Daniel Gratzer Daniel Gratzer · Accepted Answer · 2013-06-08T17:36:28

Alright, I won't answer all these questions, but I can provide some help.

If we actually try collapse on a tree that looks like this
```
          a
         / \
        /   \             
       b     c
      / \   / \
     d   e f   g
```
we'd get [d, b, e, a, f, c, g]. Notice that if an element appears "to the left" of an element in the tree, it is "to the left of" that element in our flat list. We know that if an element, a, is to the left of an element, c, in a binary search tree then a < c. So we just need to check that this property holds for our list.
Inserting an element in a tree. We have 4 cases to deal with
```
insert newVal (Node treeVal left right) | newVal < treeVal = <1>
                                        | newVal > treeVal = <2>
                                        | otherwise        = <3>
insert newVal Nil = <4>
```
where <1> is inserting into a Node with a value greater than the one in the node. <2> is the opposite: the node has a greater value than the new value. In 3 they are equal and in 4 we are inserting into Nil, the base case. You can pretty much directly translate the definition of a binary search tree to fill in the holes here.
Since we aren't trying to have a balanced binary tree, if we have 2 trees, A and B. All we have to do is find the location where the root of B would be inserted and stick the whole tree there.