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

1. 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.

2. Define a Haskell-Function insert :: Int -> Tree -> Tree which adds the Integer Value to the Tree and return also a binary search tree.

3. Define with the function insert (2) a Haskell-Function merge :: Tree -> Tree -> Tree which merges two trees to another binary search tree.

Answer 1

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

1. 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.

2. 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.

3. 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.