In this problem you have to write several functions for generic binary trees. The definition of the trees is given by:

data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show)

That is, a tree with elements of type a is, either an empty tree,
either a node with an element (of type a) and two other trees of the same type.
The *deriving (Show)* statement simply enables an visualization of trees.

- Write a function
*size :: Tree a -> Int*that, given a tree, returns its size, that is, the number of node it contains. - Write a function
*height :: Tree a -> Int*that, given a tree, returns its height, assuming that empty trees have zero height. - Write a function
*equal :: Eq a => Tree a -> Tree a -> Bool*that, given two trees, tells whether they are the same. - Write a function
*isomorphic :: Eq a => Tree a -> Tree a -> Bool*that, given two trees, tells whether they are isomorphic, that is, if one can obtain one from the other flipping some of its descendants. - Write a function
*preOrder :: Tree a -> [a]*that, given a tree, return its pre-order traversal. - Write a function
*postOrder :: Tree a -> [a]*that, given a tree, return its post-order traversal. - Write a function
*inOrder :: Tree a -> [a]*that, given a tree, return its in-order traversal. - Write a function
*breadthFirst :: Tree a -> [a]*that, given a tree, return its traversal by levels. - Write a function
*build :: Eq a => [a] -> [a] -> Tree a*that, given a pre-order traversal of a tree and an in-order traversal of the same tree, returns the original tree. You can assume that the three has no repeated elements. - Write a function
*overlap :: (a -> a -> a) -> Tree a -> Tree a -> Tree a*that, given two trees, returns its overlapping using a function. Overlapping two trees with a function consists in placing the two trees one on the other and combine the double nodes using the given function.

Scoring

Each function scores 10 points.

Public test cases

**Input**

let t7 = Node 7 Empty Empty let t6 = Node 6 Empty Empty let t5 = Node 5 Empty Empty let t4 = Node 4 Empty Empty let t3 = Node 3 t6 t7 let t2 = Node 2 t4 t5 let t1 = Node 1 t2 t3 let t1' = Node 1 t3 t2 size t1 height t1 equal t2 t3 isomorphic t1 t1' preOrder t1 postOrder t1 inOrder t1 breadthFirst t1 build [1,2,4,5,3] [4,2,5,1,3] overlap (+) t2 t3 overlap (+) t1 t3

**Output**

7 3 False True [1,2,4,5,3,6,7] [4,5,2,6,7,3,1] [4,2,5,1,6,3,7] [1,2,3,4,5,6,7] Node 1 (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty)) (Node 3 Empty Empty) Node 5 (Node 10 Empty Empty) (Node 12 Empty Empty) Node 4 (Node 8 (Node 4 Empty Empty) (Node 5 Empty Empty)) (Node 10 (Node 6 Empty Empty) (Node 7 Empty Empty))

Information

- Author
- Jordi Petit
- Language
- English
- Translator
- Jordi Petit
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- Haskell
- User solutions
- Haskell