CS 277 | lab

Learning Objectives

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

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.

NOTE: We covered this in class but you are strongly encouraged to write it from scratch yourself to make sure you understand it.

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 but returns a single list containing all values in order.

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

lab_trees