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.

Table of Contents

• Trees
• Binary Trees
• Rose Trees
• Extensions

Pre-Lab 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

1. 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/comp1100-lab09

2. 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 > project-name. 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/comp1100-lab09

3. 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, Red-Black, 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 non-empty 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 evidentially 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 Integer
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:

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

{.msg-success}
Write the treeSize function, that takes a tree, and counts the number of elements in the tree.

treeSize :: BinaryTree a -> Integer

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

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 -> Integer

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

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

Exercise 4

{:.msg-success} 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 4 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 5

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 5 treeMap

>treeMap (*2) (Node Null 3 (Node Null 5 Null))
Node Null 6 (Node Null 10 Null)

Exercise 6

Write a function elemTree that takes an Integer, and checks if it is present inside a tree of Integer’s.

elemTree :: Integer -> (BinaryTree Integer) -> Bool

Submission required: Exercise 6 elemTree

>elemTree 2 Null
False
>elemTree 3 (Node Null 4 (Node Null 3 Null))
True

Exercise 7

Write two functions, treeMaximum and treeMinimum, to find the minimum and maximum element in a tree of type Integer.

treeMaximum :: BinaryTree Integer -> Integer
treeMinimum :: BinaryTree Integer -> Integer

Submission required: Exercise 7 treeMaximum, treeMinimum

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

Write a function roseSize that counts the number of elements in a rosetree.

roseSize :: RoseTree a -> Integer

Submission required: Exercise 8 roseSize

>roseSize things
27

Exercise 9

Write a function roseLeaves that returns a list of all leaves of the rosetree.

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

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

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

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

[COMP1100 Optional, COMP1130 Compulsory]

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 it’s 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!).