Lab Trees

Assignment Description

In this lab we’ll explore some cool helper functions for binary trees, learn about creating helper functions and thinking recursively, and hopefully see some fancy ascii trees on the terminal!

A new C++ thing

We’ll be using templates again in this lab, and unfortunately, this means we have to walk into a dark scary corner of C++. But hopefully we can take our lantern and cast some light here before any compiler errors bite.

The following function definitions won’t compile:

template <typename T>
Node * BinaryTree<T>::myHelperFunction(Node * node)
// The compiler doesn't know what a Node is, since the return type isn't scoped
// with the function.

So we have to scope it:

template <typename T>
BinaryTree<T>::Node * BinaryTree<T>::myHelperFunction(Node * node)

Using g++, the latter will show an error such as:

error: expected constructor, destructor, or type conversion before '*' token

Clang gives a more helpful error message:

fatal error: missing 'typename' prior to dependent type name 'BinaryTree<T>::Node'

Without going into the ugly details of it, this is happening because your compiler thinks Node is a member variable of the BinaryTree<T> class (since it’s a template). We can resolve this issue simply by adding a nice, friendly, typename keyword before our BinaryTree<T>::Node type. This lets the compiler know that Node really is a type, not a variable:

template <typename T>
typename BinaryTree<T>::Node * BinaryTree<T>::myHelperFunction(Node * node)

The above, fixed, definition compiles correctly. Since you’ll probably want to create your own helper functions for this lab, this is important to remember when you see the strange error above. You won’t be responsible for this nuance of templates on any exam in this class.

Checking Out the Code

You can get the files for this lab by downloading lab_trees.zip.

Testing Your Code

To test your code, compile using make:

make

For a visual test, run it with:

./treefun color

You will see that the output is colored — green means correct output, red means incorrect output, and underlined red means expected output that was not present. This mode is a bit experimental, and it might cause problems with your own debugging output (or other problems in general). To turn it off, simply leave off the “color” argument:

./treefun

You may also diff your solution with our expected output:

./treefun > out
diff -u out soln_treefun.out

You can run a second set of non-visual tests with:

./test

This second set does not test all functions (in particular, those whose output is sent to standard output.) As these tests are less extensive, if your code passes ./treefun, it should pass these as well.

Helper Functions and Recursion

You’ll want to be thinking about the following problems recursively on the nodes of the tree. However, the public functions provided do not supply a Node* parameter! So, to use recursion, you’ll need to implement helper functions with an extra Node* parameter so that you can recursively act differently on different nodes. We describe an example of this below.

The height() Function

There is a function called 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.

We have implemented height() for you (see binarytree.cpp) to help you get a sense of recursive functions. Please read through the code, and ask questions if you are unsure of how it finds the height of a tree. A key point to note is that the public height() function simply calls the private height(Node* subRoot) function, so that we can recursively find the height on the subtrees.

The printLeftToRight() Function

There is a function called printLeftToRight() that prints out the values of the nodes of a binary tree in order. That is, everything to the left of a node will be printed out before that node itself, and everything to the right of a node will be printed out after that node. The function to_string(subRoot->elem) converts the elem field of a node to a string.

Note that printLeftToRight() uses an in-order-traversal to print out the nodes of a tree. You will need to use one of the three traversals covered in lecture for some of the following functions.

The mirror() Function

The mirror() function should flip our tree over a vertical axis, 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

The printPaths() Function

The printPaths()function will print out all the possible paths from the root of the tree to any leaf node —all sequences starting at the root node and continuing downwards, ending at a leaf node. Paths ending in a left node should be printed before paths ending in a node further to the right. For example, for the following tree

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

printPaths() would output

Path: 1 2 4 5
Path: 1 2 4 10
Path: 1 2 8
Path: 1 3 6
Path: 1 3 7 9

The sumDistances() Function

Good work! We just have one more function for you to write. Each node in a tree has a distance from the root node - the depth of that node, or the number of edges along the path from that node to the root. sumDistances() returns the sum of the distances of all nodes to the root node (the sum of the depths of all the nodes). Your solution should take time, where is the number of nodes in the tree. For example, on the following tree:

           __ 5 __
        __/       \__
      0               8
        \
          2
         / \
        1   4

sumDistances() should return 0+1+2+3+3+1 = 10.

OPTIONAL TASKS:

The isOrdered() Function

The isOrdered() function returns true if an in-order traversal of the tree would produce a nondecreasing list output values, and false otherwise. (This is also the criterion for a binary tree to be a binary search tree.)

For example, isOrdered() should return true on the following tree:

           __ 5 __
        __/       \__
      1               8
        \
          2
           \
            4

but false for

           __ 5 __
        __/       \__
      1               8
        \
          2
           \
            11

Hint: What conditions need to be true for a tree to be in order (as defined above)? How can we check this recursively?

FlatTree

So far we have looked at representing trees using explicit Nodes and pointers. For complete binary trees, an alternate approach is to store the elements in a vector. Instead of maintaining an explicit root and left/right pointers, we instead use the following scheme:

• the root element is stored at index 1
• the left child of an element at index i is stored at index 2*i
• the right child of an element at index i is stored at index 2*i+1

Note that the vector will have a "dummy" element at index 0, which does not correspond to any actual element in the tree.

For example, the following tree:

       2
     /   \
   4       8
  / \
 5   10

would be stored as: [X, 2, 4, 8, 5, 10], where the dummy element X can have any value.

You have the following functions to implement (in "flattree.cpp") which are documented in the corresponding header file.

• printLeftToRight
• getElement
• fromBinaryTree
• toBinaryTree

Marking Your Work

You will let us know you’ve worked on the lab by submitting your work to the autograder in PrarieLearn. We will run a very few simple test cases on your code, and if you pass any of them, you will get credit for the programming portion of the lab. (It’s a low bar.)

Submitting the lab is as simple as dragging your completed code into the PrarieLearn interface for the lab_trees assignment.

Please submit the following files:

• binarytree.cpp
• binarytree.h
• flattree.cpp
• flattree.h

Good luck!

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