Module assignment: Tree report

Why this assignment

This assignment brings every part of the module into one program. You will build a tree from input, walk it in three orders, measure its height and diameter, check its balance, print two side views, and find the lowest common ancestor of two values. Each part is a lesson you have already read, so the work is mostly about putting the pieces together without breaking one of them.

Real programs look like this. A report tool reads a data structure, runs several checks on it, and prints a summary. The hard part is rarely one clever idea. It is keeping many small functions correct at the same time, and making sure that an empty tree, a missing value or a skewed shape does not crash the program. This assignment asks you to handle those cases on purpose.

Work on it in your own folder, one file, tree_report.cpp. Compile it with g++ -std=c++17 -Wall tree_report.cpp -o tree_report and run it with the input from each example. You do not need a judge for this assignment. You check your work by comparing your output with the examples, and with the trees you draw yourself.

The task

Write a program that reads two lines from standard input and prints nine lines of report.

Line 1 is a binary tree in level order, the same format used in every lesson of this module. The values are separated by spaces. Read the root first, then the left and right children of the root, then the children of each node on the next level from left to right. Use -1 for a missing child. The line -1 by itself is an empty tree.

Line 2 holds two integers, p and q. They are the two values for the lowest common ancestor question. They are not guaranteed to be in the tree.

Your program must print exactly these nine lines, in this order:

1. preorder: followed by the preorder values, each preceded by one space.
2. inorder: followed by the inorder values, each preceded by one space.
3. postorder: followed by the postorder values, each preceded by one space.
4. height: and the height in nodes. An empty tree has height 0.
5. diameter: and the diameter in edges. An empty tree or a single node has diameter 0.
6. balanced: and the word yes or no. A tree is balanced when, at every node, the heights of the left and right subtrees differ by at most 1.
7. left view: followed by the value at the left end of each level, from the top down.
8. right view: followed by the value at the right end of each level, from the top down.
9. lca of p and q: and the lowest common ancestor value, or the word none when p or q is not in the tree.

When a list is empty, print the label alone, with no trailing space. For example, an empty tree prints the line preorder:. Print each line with a single newline at the end, and do not print any extra blank lines.

Constraints: the input has at most 1000 values. Each tree value is an integer from 0 to 999, and no two nodes in the tree share a value. The values p and q are integers from 0 to 999.

Examples

The examples show what the output must look like. Make your program print exactly these lines.

Example 1. The input is the tree from the earlier lessons, and the query is 7 and 4.

3 5 1 6 2 0 8 -1 -1 7 4
7 4

preorder: 3 5 6 2 7 4 1 0 8
inorder: 6 5 7 2 4 3 0 1 8
postorder: 6 7 4 2 5 0 8 1 3
height: 4
diameter: 5
balanced: yes
left view: 3 5 6 7
right view: 3 1 8 4
lca of 7 and 4: 2

Check a few lines by hand before you trust your program. The height is 4, because the path 3, 5, 2, 7 has four nodes. The diameter is 5, because the path 7, 2, 5, 3, 1, 0 has five edges, and no longer path exists. The left view takes the first value of each level. The levels are 3, 5 1, 6 2 0 8 and 7 4, so the left view is 3, 5, 6, 7. The right view takes the last value of each level, so it is 3, 1, 8, 4.

Example 2. The tree is unbalanced, and one of the query values is missing.

1 2 3 4 -1 -1 -1 5
5 9

preorder: 1 2 4 5 3
inorder: 5 4 2 1 3
postorder: 5 4 2 3 1
height: 4
diameter: 4
balanced: no
left view: 1 2 4 5
right view: 1 3 4 5
lca of 5 and 9: none

Node 1 has a left subtree of height 3 and a right subtree of height 1, a difference of 2, so the tree is not balanced. The value 9 is not in the tree, so the last line says none.

Example 3. The tree is empty, so most lines have no values after the label.

-1
1 2

preorder:
inorder:
postorder:
height: 0
diameter: 0
balanced: yes
left view:
right view:
lca of 1 and 2: none

The empty tree is balanced, because there is no node where the rule can fail. Notice that the program must not crash here. A common bug is to read root->left before checking root, and that crashes on an empty tree.

Requirements checklist

Use this list as you work. Each item is something the grader will check. Tick an item only after you have seen the program do it.

• The program reads line 1 with getline, and builds the tree from it, using the -1 convention.
• The line -1 alone builds an empty tree, and the program does not crash on it.
• The program reads p and q from line 2 with cin.
• Preorder, inorder and postorder are printed in the exact format, with the label and no trailing space.
• Height is counted in nodes, and the empty tree has height 0.
• Diameter is counted in edges, and it is computed in one walk that updates a best value at each node.
• Balance uses the -1 sentinel, so the walk stops as soon as a subtree is unbalanced.
• Left and right views come from one level-order walk, and each row gives one value to each view.
• The lowest common ancestor uses the one-pass recursion, and the program prints none when a value is missing.
• The program prints nothing else, and each line ends with a single newline.
• Every example above prints exactly the expected output.
• No function calls a height function at every node. Each function walks the tree a fixed number of times.

Grading rubric

Your grade depends on what the program prints on a set of hidden trees, including the empty tree, a single node, a chain that leans one way, and a random tree of about 1000 values.

60 percent. The program compiles and runs. It prints the three traversals, the height and the lca line correctly for every test, and it does not crash on the empty tree. The diameter, balance and view lines may be wrong.

80 percent. Everything in the 60 percent level is correct, and the diameter, the balance check and both views are also correct on every test. The output has the right labels and spacing for most cases, but a few empty-list lines may print a trailing space.

100 percent. Every line is correct on every test, including the empty tree, the missing query value and the lines with empty lists. The code is clean. Each function has one job, the helpers are named clearly, the walks are O(n), and no global variable carries a value from one test into the next. A reader can point to the line where each of the nine answers is produced.

A program that prints nine lines in the wrong order, or that prints a different label, loses most of the marks for the format, even when the numbers are right. The format is part of the specification.

Hints

The hints are hidden. Open each one only when you are stuck on that part. Try each part on paper first.

Reference solution

The reference solution is hidden below. Read it after you have written your own version, and compare the two line by line. Pay attention to the order of the checks, the empty-tree cases and the way each helper handles a null pointer.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
 
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front();
        q.pop();
        if (i < a.size() && a[i] != -1) {
            n->left = new TreeNode(a[i]);
            q.push(n->left);
        }
        i++;
        if (i < a.size() && a[i] != -1) {
            n->right = new TreeNode(a[i]);
            q.push(n->right);
        }
        i++;
    }
    return root;
}
 
void preorder(TreeNode* n, vector<int>& out) {
    if (!n) return;
    out.push_back(n->val);
    preorder(n->left, out);
    preorder(n->right, out);
}
 
void inorder(TreeNode* n, vector<int>& out) {
    if (!n) return;
    inorder(n->left, out);
    out.push_back(n->val);
    inorder(n->right, out);
}
 
void postorder(TreeNode* n, vector<int>& out) {
    if (!n) return;
    postorder(n->left, out);
    postorder(n->right, out);
    out.push_back(n->val);
}
 
vector<vector<int>> levels(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> row;
        for (int i = 0; i < sz; i++) {
            TreeNode* n = q.front();
            q.pop();
            row.push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        res.push_back(row);
    }
    return res;
}
 
int heightOf(TreeNode* n) {
    if (!n) return 0;
    return 1 + max(heightOf(n->left), heightOf(n->right));
}
 
// Returns the height in nodes and updates best with the longest path in edges.
int heightDiameter(TreeNode* n, int& best) {
    if (!n) return 0;
    int l = heightDiameter(n->left, best);
    int r = heightDiameter(n->right, best);
    best = max(best, l + r);
    return 1 + max(l, r);
}
 
// Returns the height, or -1 when some subtree is unbalanced.
int balanceCheck(TreeNode* n) {
    if (!n) return 0;
    int l = balanceCheck(n->left);
    if (l == -1) return -1;
    int r = balanceCheck(n->right);
    if (r == -1) return -1;
    if (abs(l - r) > 1) return -1;
    return 1 + max(l, r);
}
 
TreeNode* findNode(TreeNode* n, int v) {
    if (!n) return nullptr;
    if (n->val == v) return n;
    TreeNode* l = findNode(n->left, v);
    if (l) return l;
    return findNode(n->right, v);
}
 
TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* l = lca(root->left, p, q);
    TreeNode* r = lca(root->right, p, q);
    if (l && r) return root;
    return l ? l : r;
}
 
void printList(const string& label, const vector<int>& v) {
    cout << label;
    for (int x : v) cout << " " << x;
    cout << "\n";
}
 
int main() {
    string treeLine;
    getline(cin, treeLine);
    istringstream in(treeLine);
    vector<int> values;
    int x;
    while (in >> x) values.push_back(x);
    TreeNode* root = build(values);
 
    int p, q;
    cin >> p >> q;
 
    vector<int> pre, ino, post;
    preorder(root, pre);
    inorder(root, ino);
    postorder(root, post);
    printList("preorder:", pre);
    printList("inorder:", ino);
    printList("postorder:", post);
 
    cout << "height: " << heightOf(root) << "\n";
    int best = 0;
    heightDiameter(root, best);
    cout << "diameter: " << best << "\n";
    cout << "balanced: " << (balanceCheck(root) != -1 ? "yes" : "no") << "\n";
 
    vector<int> left, right;
    for (auto& row : levels(root)) {
        left.push_back(row.front());
        right.push_back(row.back());
    }
    printList("left view:", left);
    printList("right view:", right);
 
    TreeNode* a = findNode(root, p);
    TreeNode* b = findNode(root, q);
    cout << "lca of " << p << " and " << q << ": ";
    if (!a || !b) {
        cout << "none\n";
    } else {
        cout << lca(root, a, b)->val << "\n";
    }
    return 0;
}

Why the reference is built this way

Each part of the reference is a function you have already seen, and the main function only calls them in order. That shape is what makes the program easy to test. If the balance line is wrong, you look only at balanceCheck. You do not have to read the traversals or the views.

The order of the checks in main matters. The traversals and the height come first, because they work on an empty tree without any special case. The lowest common ancestor comes last, because it is the only part that can receive a null pointer from a missing query value. Put the risky part last, after the safe parts have printed, and check its inputs before you use them.

The helper printList prints the label, then one space before each value. For an empty list, the loop prints nothing, so the line is the label alone. That is why the empty tree prints preorder: with no trailing space. Writing the spacing in one helper, instead of in nine places, is the simplest way to keep the format exact.

Notice the best variable in main. It is a local variable that starts at 0 for every run, so nothing carries over from one test to another. That is the rule from the lesson on height: pass state in, and do not rely on a global that the program never resets.

Submitting your work

Keep the file tree_report.cpp in your own folder. Before you submit, run the program on the three examples and compare every line. Then run it on at least four trees you made up, and check each of the nine lines by hand on paper. Choose one of the trees to be empty, one to be a single node, one to be a chain that leans to the left, and one to be a balanced tree with seven values. For each tree, write down the answers first, and only then run the program.

A short note at the top of your file helps the grader. Say which test cases you checked, and say which function you were least sure about. Honest notes about remaining doubts are better than a claim that everything works.