This practical gives you some more practice in programming with binary trees. Download the file nodes.cpp and extendedBST.cpp. The first is a template to use in completing question 1, and the second is the BST class file extended with functions you need for completing your function. Use g++ extendedBST.cpp.

1. (*) Implement a recursive function to compute the sum of the values at the leaves in a binary search tree. Use the templates given above.

2. Experiment with depth first search and breadth first search introduced in lectures implemented in the binary search tree class. Create trees which have the following depth first search outputs.
   1. Tree 1 has depth first search output: 4 2 1 3 5, breadth first search output: 4 2 5 1 3

   2. Tree 2 depth first search output: 6 5 4 1 2 3 breadth first search output: 6 5 4 1 2 3

   3. How would you change the implementations to obtain a depth first search which explores the paths from right to left, and a breadth first search which explores the levels from right to left?
   Answers to all of the above starred questions should be submitted into the online system by Monday morning of Week 7. Please submit the file nodes.cpp, and remember to remove your "int main()..." if you use one there.

   All enquiries to Annabelle McIver