Goals

To implement different tree traversals and get practice with recursion.

Setup

Mount the COURSES drive and remember to save everything into STUWORK. If you don’t do this, everything you write will disappear when you log out!!!!

  • Create a new folder in your STUWORK called TreeTraversalsLab
  • Download the starter code and put it into your lab folder
  • Open your TreeTraversalsLab folder in VSCode

Exercise 1

  1. Look at the code in main for creating a tree and draw out what you think the tree will look like on the back of your worksheet.

  2. Write out on paper what each traversal order (pre, post, in) should result in for your tree.

Exercise 2

Implement each of the traversals, making sure to test your code as you go. (I.e. you should check after implementing each method that it works!)

Exercise 3

What is the worst case time complexity of traversing a tree? What about getting to just a leaf?

Upload your completed lab to Moodle for an extra engagement credit.

Extra

We don’t have an easy way to add to our tree yet, start thinking about how you could add to the tree. There are both easy ways and difficult ways, depending on how much you care about keeping the tree in order. Think about the trade-offs and try out some implementations. We’ll learn more about particular ways to add to particular trees in the coming days.