Week 11: Exercises

Solve the following problems in Haskell.

1. Tree Fold

1. Write a function treeFoldr that performs a right fold of a function over the values in a binary tree.

2. Use treeFoldr to write functions that

   • add all the values in a binary tree of numbers;

   • generate a list containing all the values in a binary tree

2. Balance Test

Define a balanced tree as follows: for any node, the number of nodes in the left and right subtrees differ by at most 1.

Write a function isBalanced that determines whether a tree is balanced. What is your function's worst-case big-O running times?