Please read the remarks about programming problems for this course.

A binary tree may be traversed in one of three standard ways:

It is not possible to deduce a binary tree's structure solely from the order of the list of elements visited during a single traversal. It is possible, however, to construct a binary tree from a preorder and an inorder traversal.

Given a binary tree node defined as

template <typename T> struct Node { T data; Node *left; Node *right; Node(const T& d, Node *lf, Node *rt) : data(d), left(lf), right(rt) {} };

complete the following function that constructs a binary tree given iterators to both preorder and inorder traversals:

template <typename T> Node<T> *build_tree(typename vector<T>::iterator pre_begin, typename vector<T>::iterator pre_end, typename vector<T>::iterator in_begin, typename vector<T>::iterator in_end) { // Add your code here }

To check that your function is correct, supply the missing code in the following tandem of overloaded functions that together draw a binary tree sideways:

template <typename T> void draw(Node<T> *tree, char link, int depth) { // Add your code here } template <typename T> void draw(Node<T> *tree) { draw(tree, '-', 0); }
Note that you need implement the first function only—the second function is complete.

When executed, the following client code fragment

// Specify a preorder and inorder traversal vector<int> pre = { 36, 100, 11, 3, 10, 5, 2, 8 }, in = { 11, 100, 10, 3, 5, 36, 8, 2 }; // Build the binary tree from the traversals Node<int> *tree = build_tree<int>(begin(pre), end(pre), begin(in), end(in)); // Draw the resulting tree draw(tree);

should produce the following output:

/[2] \[8] -[36] /[5] /[3] \[10] \[100] \[11]

(Rotate your head 90 degrees counter-clockwise to see the tree as we normally would orient it.) This output corresponds to the following graphical rendering of the tree:

Binary tree picture

Hint: Notice that the draw function performs a backwards inorder traversal (right subtree, node, left subtree), and the depth of the recursion controls the amount of horizontal space to the left of the printed node.

When you have implemented and tested the two functions, place them in a file named treetrav.cpp. Include the expected comments, but do not include any other code besides the two function definitions—this is because I will #include your file into my test code.

You may believe that it would be a good idea to provide a function to free up the space held by a binary tree that a client created via your build_tree function. The following should work nicely:

template <typename T> void dispose_tree(Node<T> *t) { if (t) { dispose_tree(t->left); dispose_tree(t->right); delete t; } }

You do not need to provide this function, as my test code takes care of it for you. You probably want to add this code to your test code.

Since it can be challenging to write both draw and build_tree at the same time, I suggest writing draw first. You can use the following code to test your draw function:

Node<int> *sample_tree = new Node<int>(14, new Node<int>(11, new Node<int>(12, nullptr, nullptr), new Node<int>(5, nullptr, nullptr)), new Node<int>(6, nullptr, new Node<int>(5, nullptr, nullptr))); draw_tree(sample_tree);

If your draw function is correct, the above code should display the following:

/[5] /[6] -[14] /[5] \[11] \[12]

Once you get draw working you can use it to verify that your build_tree function is correct. (You also can check your build_tree function by doing preorder and postorder traversals on the tree it returns and comparing the result to the original traversals.)

Submit your completed treetrav.cpp source file to eclass.e.southern.edu.