In this lab we cover the concept of trees, how they differ to lists, and how we can write recursive functions that operate on trees.
PreLab Checklist
 You understand the concept of higher order functions and how to apply them.
 You can write recursive functions over lists and numbers.
 You are familiar with pattern matching against abstract data types.
Getting Started

Go to the project’s dashboard under the Project tab and click on the Fork button. The gitlab url for this lab is https://gitlab.cecs.anu.edu.au/comp1100/2023s2/studentfiles/lab091100_s2_2023

You will be asked where to fork the repository. Click on the user or group to where you’d like to add the forked project. You should see your own name here. Once you have successfully forked a project, you will be redirected to a new webpage where you will notice your name before
> projectname
. This means you are now the owner of this repository. The url in your browser should reflect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab091100_s2_2023 
Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
This lab contains additional exercises for COMP1130 students. COMP1100 students are encouraged to attempt them once they have completed the compulsory exercises to receive the participation marks for the lab.
Trees
So far the only recursive data structure we’ve really seen are lists. Lists are useful for packing many elements of the same type together, but sometimes they can be a hindrance from an efficiency perspective. When we are trying to find the last element in a list, we always have to traverse through all elements, even if we know how long the list is. We will see more about the benefits of trees in next lab when we cover binary search trees, but for this lab, we consider two kinds of trees, binary and rose.
Binary Trees
There are many different kinds of trees (Rose, AVL, RedBlack, Quad) but we will concentrate on the simplest kind of trees for the moment, Binary Trees. Binary Trees have a recursive definition, similar to lists:
A binary tree (containing elements of type a
) is either:
 An empty, or null tree. (This is the base case for Binary Trees, like the empty list for Lists.)
 A node, which contains an element of type
a
, and two more binary trees, called subtrees. (This is the step case for Binary Trees, like how the step case for a list was an element, attached to another list).
Here is corresponding Haskell data type:
data BinaryTree a = Null  Node (BinaryTree a) a (BinaryTree a)
Note how similar this is to the definition for a list, except each nonempty list is an element, followed by exactly one other list. We call the two subtrees the left subtree and the right subtree respectively.
How a tree is structured is best seen graphically.
A lot of the terminology relating to trees is borrowed from that of real life trees.
Computer scientists, having spent their entire life in front of a computer and never gone outside, have evidently forgotten that trees are supposed to grow up, not down.
We call the node at the very top of the tree the root node. The nodes down at the bottom that only have empty subtrees beneath them are called leaves.
Unfortunately the same tree doesn’t read as nicely when expressed using our recursive definition. Due to the way trees branch (just like their real life counterparts) they are difficult to display textually.
Written out directly,
tree1 :: BinaryTree Int
tree1 = Node (Node (Node Null 2 (Node Null 11 Null)) 4 (Node (Node Null 0 Null)
1 (Node Null (3) Null))) 5 (Node (Node (Node Null (4) Null) 8
(Node Null 7 Null)) 3 Null)
There’s no clear correspondence between how Haskell stores the tree
and the graphical picture of the tree. We’ve included some code in
DrawTree.hs
that Lab09.hs
imports, so you can use the function
printTree
(don’t worry about how it works) which will print the
trees graphically. You may find it useful to play with and to help you
visualise the output of functions.
>printTree tree1
5

+ 3
 
 + Null
 
 ` 8
 
 + 7
  
  + Null
  
  ` Null
 
 ` 4
 
 + Null
 
 ` Null

` 4

+ 1
 
 + 3
  
  + Null
  
  ` Null
 
 ` 0
 
 + Null
 
 ` Null

` 2

+ 11
 
 + Null
 
 ` Null

` Null
We can pattern match against binary trees in a similar way to
pattern matching against lists. Here is a list of useful patterns you might
need. Note that there is nothing special about using the variables
left
or right
to pattern match against, but it’s just a bit more
readable that way:
Pattern  Description  Example 

Null 
The (unique) empty tree  Null 
Node left x right 
A nonempty tree  Anything that isn’t Null . 
Node Null x Null 
A tree with no subtrees (called a leaf)  Node Null 3 Null , Node Null "hello" Null 
Node Null x right 
A nonempty tree, with no left subtree  Node Null 3 (Node Null 4 Null) , Node Null 10 Null 
Node left 8 right 
A nonempty tree with 8 as the element  Node (Node Null 4 Null) 8 Null , Node Null 8 (Node Null 5 Null) 
Now, with that in mind, we can start to write some functions on trees. We can write recursive functions operating over trees, just the same as we did over lists, using the patterns described above.
For the following exercises, have some pen and paper available to hand draw test cases before entering them into Haskell.
Exercise 1 Tree Size
Write the treeSize
function, that takes a tree, and counts the
number of elements in the tree.
treeSize :: BinaryTree a > Int
Hint: Recall the function we wrote in Lab 6,
lengthList
, that would take a list and return the number of
elements.
Submission required: Exercise 1 treeSize
Exercise 2 Tree Depth
Write a function treeDepth
that computes the depth of a tree, which
is defined as the length of the longest path from the root node down
to any leaf.
treeDepth :: BinaryTree a > Int
Submission required: Exercise 2 treeDepth
Note that the same number of nodes can be rearranged into trees of different depth, as demonstrated below.
> treeDepth Null
0
> treeDepth (Node Null 3 Null)
1
> treeDepth (Node (Node Null 1 Null) 2 (Node Null 3 Null))
2
> treeDepth (Node Null 1 (Node Null 2 (Node Null 3 Null)))
3
You might like to contemplate if the size and depth of a tree are related in anyway. (Given you know the size of a tree, what possible values of the depth can there be?)
Exercise 3 Tree leaves
Write a function leavesTree
that takes a tree, and
returns a list containing only the elements in leaf nodes.
leavesTree :: BinaryTree a > [a]
Submission required: Exercise 3 leavesTree
> leavesTree Null
[]
> leavesTree (Node Null 3 Null)
[3]
> leavesTree (Node (Node Null 1 Null) 2 (Node Null 3 Null))
[1,3]
> leavesTree (Node Null 1 (Node Null 2 (Node Null 3 Null)))
[3]
Exercise 4 Map function for trees
Write a function treeMap
that works analogously to map
, by
applying a function to each node in a tree.
treeMap :: (a > b) > (BinaryTree a) > (BinaryTree b)
Submission required: Exercise 4 treeMap
> treeMap (*2) (Node Null 3 (Node Null 5 Null))
Node Null 6 (Node Null 10 Null)
Exercise 5 Searching a tree
Write a function elemTree
that takes an Int
, and checks if it is
present inside a tree of Int
’s.
elemTree :: Int > (BinaryTree Int) > Bool
Submission required: Exercise 5 elemTree
> elemTree 2 Null
False
> elemTree 3 (Node Null 4 (Node Null 3 Null))
True
Exercise 6 Minimum and maximum element in a tree
Write two functions, treeMaximum
and treeMinimum
, to find the
minimum and maximum element in a tree of type Int
.
treeMaximum :: BinaryTree Int > Int
treeMinimum :: BinaryTree Int > Int
Submission required: Exercise 6 treeMaximum
, treeMinimum
Exercise 7 Flatten Binary Tree
Write a function flattenTree
that takes a tree, and returns a list
containing all the elements from that tree. We call such an operation
“flattening” a tree.
flattenTree :: BinaryTree a > [a]
Submission required: Exercise 7 flattenTree
> flattenTree Null
[]
> flattenTree (Node Null 3 Null)
[3]
> flattenTree (Node (Node Null 1 Null) 2 (Node Null 3 Null))
[1,2,3]
> flattenTree (Node Null 1 (Node Null 2 (Node Null 3 Null)))
[1,2,3]
Note that by flattening the tree, we lose some information, namely how the tree itself was structured.
You can sanity check the result by testing for some example trees (or the example trees provided) that
length (flattenTree tree) == treeSize tree
That is, that the number of elements in the flattened list, is the same as the number of elements originally in the tree.
Rose Trees
Binary trees are characterised by the property that each node has exactly two children. Rose trees are different, in that each node can have any number of children (including none).
RoseTree a = RoseNode a [RoseTree a]
Note that there is no empty case like there is for our definition of a
BinaryTree
. (What’s the closest thing we can get to the empty tree
under this definition?)
Rose trees can have a different number of children for each node,
there’s no constraint on how few (or how many) there must be. We’ve
included the following tree things :: RoseTree String
as an example
for you to use.
Rose trees can be useful for games (like Chess), as you can draw out all your possible moves, and all of your opponents possible responses, and all of your responses to their responses, and so on.
Exercise 8 Size of Rose Tree
Write a function roseSize
that counts the number of elements in a rose tree.
roseSize :: RoseTree a > Int
Submission required: Exercise 8 roseSize
> roseSize things
27
Exercise 9 Leaves of a Rose Tree
Write a function roseLeaves
that returns a list of all leaves of the rose tree.
roseLeaves :: RoseTree a > [a]
You can test your function by counting the number of leaves in the rose tree things
.
> length (roseLeaves things)
16
Submission required: Exercise 9 roseLeaves
> roseLeaves things
["cat", "dog", "steel", "bronze", "gold", ...]
Exercise 10 Flatten Rose Tree
Write a function roseFlatten
that returns a list of all elements in the rosetree.
roseFlatten :: RoseTree a > [a]
Submission required: Exercise 10 roseFlatten
> roseFlatten things
["thing", "animal", "cat", "dog", "metal", "alloy", "steel", ...]
> length (roseFlatten things)
27
Exercise 11 Map function for Rose Tree
Write a function roseMap
that takes a function, and applies it to every element of a rosetree.
roseMap :: (a > b) > RoseTree a > RoseTree b
Submission required: Exercise 11 roseMap
Test the result by mapping the function allCaps
to the rosetree things
.
All the elements should now be written in uppercase.
Exercise 12 Binary Tree to Rose Tree
Write a function binaryTreeToRose
that converts a binary tree to a
rosetree.
The new rose tree should have the same structure as the binary tree.
binaryTreeToRose :: BinaryTree a > RoseTree a
Submission required: Exercise 12 binaryTreeToRose
>binaryTreeToRose (Node (Node Null 1 Null) 2 (Node Null 3 Null))
RoseNode 2 [RoseNode 1 [],RoseNode 3 []]
You are required to submit your attempts at the exercises above in order to receive full participation marks for this lab. You have until the start of your next lab to do this. You should submit by committing and pushing all your changes to your Gitlab repository.
Extension (Optional)
Extension 1
Write a function isBalanced
that verifies if a tree is “balanced”,
that is, there is no other way to restructure the tree such that it
has smaller depth.
isBalanced :: BinaryTree a > Bool
Submission optional: Extension 1 isBalanced
For example, given the elements \(\{1,2,3,4,5\}\), a balanced tree containing those elements is shown below. Note that a tree of depth 2 can hold at most 3 elements (why?) so we had to use a depth 3 tree. (Note that this is not the only way to arrange these elements into a tree. Can you find another?)
(Hint: How can we related the number of elements in a tree to its depth, and what do these quantities tell us about the tree being balanced or not?)
Consider: Why might it be advantageous to have a balanced binary tree? Chat with your peers and tutor if you are unsure. We will investigate the benefits of enforcing a certain structure on complex data types in future labs (and courses!).