Trees Solutions
Question: Draw Your Own Trees
Below we have written out two instances of Binary Trees. Draw each one:
Node (Node Null -5 Null) 10 (Node Null 7 Null)
Node (Node (Node Null 'a' Null) 'b' (Node Null 'c' Null)) 'd' (Node (Node Null 'e' Null) 'f' Null)
Answers:
Now we have drawn some example trees. Convert them to Haskell and write their type:
Answers:
Node (Node Null "was" Null) "I" (Node Null "will" Null)
. Type:BinaryTree String
.Node (Node (Node Null 1 Null) 3 (Node Null 2 Null)) 4 (Node (Node Null 1 Null) 1 Null)
. Type:BinaryTree Int
.
Question: Binary Tree Functions
- Write a function
treeNodes
that counts the total number of nodes in a binaryTree. For example:
treeNodes (Node (Node (Node Null 1 Null) 2 Null) 3 (Node (Node (Node Null 4 Null) 5 Null) 6 (Node (Node Null 7 Null) 8 (Node (Node Null 9 (Node Null 10 Null)) 11 (Null))))) = 11
Answer:
treeNodes :: BinaryTree a -> Int
treeNodes tree = case tree of
Null -> 0
Node (leftTree) _ (rightTree) -> 1 + (treeNodes leftTree) + (treeNodes rightTree)
- Write a function to calculate the depth of a tree. (See above for definition and example). For example:
treeDepth (Node (Node (Node Null 1 Null) 2 Null) 3 (Node (Node (Node Null 4 Null) 5 Null) 6 (Node (Node Null 7 Null) 8 (Node (Node Null 9 (Node Null 10 Null)) 11 (Null))))) = 6
Answer:
treeDepth :: BinaryTree a -> Int
treeDepth tree = case tree of
Null -> 0
Node (leftTree) _ (rightTree) -> 1 + (max (treeDepth leftTree) (treeDepth rightTree))
- Write a
treeMap
function that maps a function to all the values inside a tree. For example:
treeMap (+1) (Node (Node (Node Null 1 Null) 2 Null) 3 (Node (Node (Node Null 4 Null) 5 Null) 6 (Node (Node Null 7 Null) 8 (Node (Node Null 9 (Node Null 10 Null)) 11 (Null)))))
= Node (Node (Node Null 2 Null) 3 Null) 4 (Node (Node (Node Null 5 Null) 6 Null) 7 (Node (Node Null 8 Null) 9 (Node (Node Null 10 (Node Null 11 Null)) 12 Null)))
Answer:
treeMap :: (a-> b ) -> BinaryTree a -> BinaryTree b
treeMap f tree = case tree of
Null -> Null
Node (leftTree) a (rightTree) -> Node (treeMap f leftTree) (f a) (treeMap f rightTree)
Question: Draw Rose Trees
- Now that you understand what a rose tree is, draw the rose tree corresponding to the following code representation:
Rose 15 [Rose 3 [], Rose 5 [Rose 1 [], Rose 3 [], Rose 7 []]]
Answer:
- Now write out the haskell code that would correspond to the following rose tree:
Answer:
Rose 'A' [Rose 'B' [Rose 'E' []], Rose 'C' [], Rose 'D' [Rose 'F' [], Rose 'G' []]
Question: Rose Tree Functions
Implementing functions that operate on rose trees is very similar to Binary trees, however, instead of recursing to the left child and right child, you will need to iterate through the entire list of children. With this in mind, implement the Binary tree functions you implemented earlier for Rose trees.
- Implement
roseTreeNumNodes
which takes a rose tree and returns the number of nodes.
Answer:
data Rose a = Rose a [Rose a]
deriving (Show)
roseTreeNumNodes :: (Rose a) -> Integer
roseTreeNumNodes (Rose a children) = 1 + sum (map roseTreeNumNodes children)
- Implement
roseTreeHeight
which takes a rose tree and returns the height.
Answer:
data Rose a = Rose a [Rose a]
deriving (Show)
roseTreeHeight :: (Rose a) -> Integer
roseTreeHeight (Rose a children) = 1 + foldl max (0) (map roseTreeHeight children)
- Implement
roseTreeMap
which takes a function and a rose tree and recursively applies that function to every element of the rose tree.
Answer:
data Rose a = Rose a [Rose a]
deriving (Show)
roseTreeMap :: (a -> b) -> (Rose a) -> Rose b
roseTreeMap f (Rose x children) = Rose (f x) (map (roseTreeMap f) children)