lab_trees

Learning Objectives

• Practice storing information in a binary tree
• Implement structural functions and traversal functions
• Practice manipulating tree structures while preserving content

Submission Instructions

Using the Prairielearn workspace, test and save your solution to the following exercises. (You are welcome to download and work on the files locally but they must be re-uploaded or copied over to the workspace for submission).

Assignment Description

In this lab we’ll explore some cool functions for binary trees, practice manipulating tree structures, and hopefully see some fancy ascii trees on the terminal! Most functions in this lab will require (or at least be significantly easier!) with helper functions.

Binary Tree Height

# INPUT:
# None
# OUTPUT:
# the height of a binary tree
int binaryTree.height():

Write a function binaryTree.height() that returns the height of the binary tree. Recall that the height of a binary tree is just the length of the longest path from the root to a leaf, and that the height of an empty tree is -1.

HINT: If you get stuck, take a look at the lecture slides! We covered the recursion necessary to solve this problem in class and your task is to implement it.

NOTE: A function to print a tree has been provided to assist you with your debugging. It will only work once you have successfully implemented height (as it calls the height function to properly print the tree).

In-Order Traversal

# INPUT:
# None
# OUTPUT:
# A list containing the in-order traversal of the binaryTree
# NOTE: The traversal returns a list NOT a print like in-class examples
list[int] binaryTree.inOrder():

In class we covered both pre- and post-order traversal using print statements. Here you must write an in-order traversal that does not print each value in order and instead returns a single list containing all values in order. This is slightly harder than the problem covered in class but still follows the broad strokes of our previous implementations.

Recall that in-order traversal works as follows: For each node in the tree, everything to the left of the node will be listed before the node, and everything to the right of the node will be listed after that node.

Mirroring a tree

# INPUT:
# None
# OUTPUT:
# Nothing
# mirror should flip the tree around the root
None binaryTree.mirror():

The mirror() function is a good exercise in understanding both recursive traversals through a tree and how to adjust a tree’s structure. When called, the function should flip the binaryTree tree over a vertical axis through the root by modifying the tree itself (not creating a flipped copy).

For example, if our original tree was

                        ______ 8 ______
                 ______/               \______
            __ 5 __                            9 __
         __/       \__                             \__
       2               7                               10
     /   \           /
   1       4       6
          /
         3

Our mirrored tree would be

                        ______ 8 ______
                 ______/               \______
            __ 9                            __ 5 __
         __/                             __/       \__
       10                              7               2
                                         \           /   \
                                           6       4       1
                                                    \
                                                     3

When solving this problem, you should break it down as a recursive exercise – what is the simplest possible mirror (base case)? What is my recursive step? How do I combine recursive calls to modify the existing tree rather than return a mirrored copy?

HINT: Mirror is an interesting recursive exercise because the actual changes to the structure don’t actually happen in the base case but the recursive step.

Citations

Thanks to Nick Parlante/Stanford, Princeton’s CS 126, and CS 473 Spring 2011 for the exercises and inspiration.