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!
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::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.
You can get the files for this lab by downloading lab_trees.zip.
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.
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.
height() FunctionThere 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.
printLeftToRight() FunctionThere 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.
IMPORTANT! Print a space after each element. This means that there will be an extra space after the last element.
mirror() FunctionThe mirror() function should flip our tree over a vertical axis, modifying the tree itself (not creating a flipped copy).
printPaths() FunctionThe 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
IMPORTANT! Print a space after each element. This means that there will be an extra space after the last element.
sumDistances() FunctionGood 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
isOrdered() FunctionThe 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.)
Hint: What conditions need to be true for a tree to be in order (as defined above)? How can we check this recursively?
binarytree.cpp
/**
* @file binarytree.cpp
* Definitions of the binary tree functions you'll be writing for this lab.
* You'll need to modify this file, as well as binarytree.h.
*/
#include <iostream>
using namespace std;
/**
* @return 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.
*/
template <typename T>
int BinaryTree<T>::height() const
{
// Call recursive helper function on root
return height(root);
}
/**
* Private helper function for the public height function, with an additional
* Node* parameter to allow for recursive calls. NOTE: use this as an example
* for writing your own private helper functions.
* @param subRoot
* @return The height of the subtree.
*/
template <typename T>
int BinaryTree<T>::height(const Node* subRoot) const
{
// Base case
if (subRoot == NULL)
return -1;
// Recursive definition
return 1 + max(height(subRoot->left), height(subRoot->right));
}
/**
* 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.
*/
template <typename T>
void BinaryTree<T>::printLeftToRight() const
{
// Your code here
printLeftToRight(root);
// Do not remove this line - used for correct print output
cout << endl;
}
template <typename T>
void BinaryTree<T>::printLeftToRight(const Node* subRoot) const
{
// Base case
if (subRoot == NULL) return;
printLeftToRight(subRoot->left);
cout << to_string(subRoot->elem) << " ";
printLeftToRight(subRoot->right);
}
/**
* Flips the tree over a vertical axis, modifying the tree itself
* (i.e. not creating a flipped copy).
*/
template <typename T>
void BinaryTree<T>::mirror()
{
mirror(root);
}
template <typename T>
void BinaryTree<T>::mirror(Node*& subRoot) const
{
if (subRoot == NULL) return;
Node* temp = subRoot->left;
subRoot->left = subRoot->right;
subRoot->right = temp;
mirror(subRoot->left);
mirror(subRoot->right);
}
/**
* Prints out all the possible paths from the root of the tree to any leaf node.
* That is, 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.
*/
template <typename T>
void BinaryTree<T>::printPaths() const
{
// Your code here
vector<vector<string>> paths;
vector<string> currentPath = {};
getPaths(root, currentPath, paths);
for (unsigned long i = 0; i < paths.size(); i++) {
cout << "Path: ";
for (unsigned long j = 0; j < paths[i].size(); j++) {
cout << paths[i][j] << " ";
}
cout << endl;
}
}
template <typename T>
void BinaryTree<T>::getPaths(Node* subRoot, vector<string>& currentPath, vector<vector<string>>& allPaths) const
{
if (subRoot == NULL) return;
currentPath.push_back(to_string(subRoot->elem));
if (subRoot->left == NULL && subRoot->right == NULL) {
allPaths.push_back(currentPath);
} else {
getPaths(subRoot->left, currentPath, allPaths);
getPaths(subRoot->right, currentPath, allPaths);
}
currentPath.pop_back();
}
/**
* 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. This
* function 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 O(n) time,
* where n is the number of nodes in the tree.
* @return The sum of the distances of all nodes to the root.
*/
template <typename T>
int BinaryTree<T>::sumDistances() const
{
return sumDistances(root, 0);
}
template <typename T>
int BinaryTree<T>::sumDistances(Node* subRoot, int depth) const
{
if (subRoot == NULL) return 0;
// Sum the distances for the left and right subtrees
int leftSum = sumDistances(subRoot->left, depth + 1);
int rightSum = sumDistances(subRoot->right, depth + 1);
return depth + leftSum + rightSum;
}
/**
* @return 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.
*/
template <typename T>
bool BinaryTree<T>::isOrdered() const
{
T lastElem = numeric_limits<T>::min();
return isOrdered(root, lastElem);
}
template <typename T>
bool BinaryTree<T>::isOrdered(Node* subRoot, T& lastElem) const
{
if (subRoot == NULL) return true;
if (!isOrdered(subRoot->left, lastElem)) return false;
if (subRoot->elem < lastElem) return false;
lastElem = subRoot->elem;
return isOrdered(subRoot->right, lastElem);
}
binarytree.h
/**
* @file binarytree.h
* Declaration of the BinaryTree class. You MUST modify this file
* to add private helper functions (see below).
*/
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
/**
* The BinaryTree class represents a templated linked-memory tree data
* structure.
*/
template <typename T>
struct BinaryTree
{
/**
* Represents a tree node; that is, an element in a BinaryTree.
* It has a data element and pointers to its left and right children.
*/
struct Node {
T elem;
Node* left;
Node* right;
/**
* Node element constructor; sets children to point to NULL.
* @param element The templated data element that the constructed
* node will hold.
*/
Node(const T& element) : elem(element), left(NULL), right(NULL)
{
/* nothing */
}
};
/**
* Constructor to create an empty tree.
*/
BinaryTree();
/**
* Copy constructor.
*/
BinaryTree(const BinaryTree& other);
/**
* Destructor; frees all nodes associated by this tree.
*/
~BinaryTree();
/**
* Assignment operator.
* @param rhs The tree to make a copy of.
* @return A reference to the current tree.
*/
const BinaryTree& operator=(const BinaryTree& rhs);
/**
* Frees all nodes associated with this tree and sets it to be empty.
*/
void clear();
/**
* Inserts into the BinaryTree.
* @param elem The element to insert
* @param sorted By default, this parameter is false. That means that the
* element takes a pseudo-random path to a leaf where it is inserted. If
* true, the insert function will act like it does in a BST.
*/
void insert(const T& elem, bool sorted = false);
/**
* Prints the contents of the tree to stdout.
*/
void print() const;
/**
* This lab deals with the following six helper functions:
*/
/**
* @return 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.
*/
int height() const;
/**
* 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.
*/
void printLeftToRight() const;
/**
* Flips the tree over a vertical axis, modifying the tree itself
* (not creating a flipped copy).
*/
void mirror();
/**
* Prints out all the possible paths from the root of the tree to any leaf
* node.
* That is, 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.
*/
void printPaths() const;
/**
* 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.
* This function 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
* O(n) time, where n is the number of nodes in the tree.
* @return The sum of the distances of all nodes to the root.
*/
int sumDistances() const;
/**
* @return 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.
*/
bool isOrdered() const;
Node* root;
mt19937 rng;
private:
/**
* Private helper function for the public height function.
* @param subRoot The current node in the recursion.
* @return The height of the subtree.
*/
int height(const Node* subRoot) const;
/**
* IMPORTANT: Put your own private helper functions below this
* comment. Look at the private helper for height as an example.
*/
void printLeftToRight(const Node* subRoot) const;
void mirror(Node*& subRoot) const;
void getPaths(Node* subRoot, vector<string>& currentPath, vector<vector<string>>& allPaths) const;
int sumDistances(Node* subRoot, int depth) const;
bool isOrdered(Node* subRoot, T& lastElem) const;
/**
* Private helper function for the public insert function.
* @param node The current node in the recursion.
* @param elem The element to insert.
* @param sorted By default, this parameter is false. That means that the
* element takes a pseudo-random path to a leaf where it is inserted. If
* true, the insert function will act like it does in a BST.
*/
void insert(Node*& node, const T& elem, bool sorted);
/**
* Helper function for operator= and cctor.
* @param subRoot The current node in the recursion.
*/
Node* copy(const Node* subRoot);
/**
* Private helper function for clear that clears beneath the parameter node.
* @param subRoot The current node in the recursion.
*/
void clear(Node* subRoot);
};
#include "binarytree_given.cpp"
#include "binarytree.cpp"
#endif