Challenge: Leaves and Totals

Lab C++ Intermediate 20 points

Print the number of nodes, the number of leaves, and the largest value.

Input

One line: the tree in level order (row by row, left to right), with N for a missing child. For example 1 2 3 N 4 is 1 with children 2 and 3, where 2 has only a right child 4. The starter code already builds the tree for you.

Output

Nodes: <n>
Leaves: <n>
Max: <value>

Example

Input

8 3 10 1 6 N 14 N N 4

Output

Nodes: 7
Leaves: 3
Max: 14

Sample input available Sample output available

Editor

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

// Build a tree from level-order values on one line; "N" means no node.
Node* buildTree(const string& line) {
    istringstream in(line);
    vector<string> t;
    string tok;
    while (in >> tok) t.push_back(tok);
    if (t.empty() || t[0] == "N") return nullptr;
    Node* root = new Node(stoi(t[0]));
    queue<Node*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < t.size()) {
        Node* node = q.front();
        q.pop();
        if (t[i] != "N") { node->left = new Node(stoi(t[i])); q.push(node->left); }
        i++;
        if (i < t.size() && t[i] != "N") { node->right = new Node(stoi(t[i])); q.push(node->right); }
        i++;
    }
    return root;
}

int main() {
    string line;
    getline(cin, line);
    Node* root = buildTree(line);
    // Solve the task using root
    return 0;
}

Hints

A leaf has no children.

For the max, an empty tree can return the smallest int.

Solution explanation

Three small recursive functions, each O(n).

Show solution

#include <algorithm>
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

// Build a tree from level-order values on one line; "N" means no node.
Node* buildTree(const string& line) {
    istringstream in(line);
    vector<string> t;
    string tok;
    while (in >> tok) t.push_back(tok);
    if (t.empty() || t[0] == "N") return nullptr;
    Node* root = new Node(stoi(t[0]));
    queue<Node*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < t.size()) {
        Node* node = q.front();
        q.pop();
        if (t[i] != "N") { node->left = new Node(stoi(t[i])); q.push(node->left); }
        i++;
        if (i < t.size() && t[i] != "N") { node->right = new Node(stoi(t[i])); q.push(node->right); }
        i++;
    }
    return root;
}

int countNodes(Node* n) { return n ? 1 + countNodes(n->left) + countNodes(n->right) : 0; }
int leaves(Node* n) {
    if (!n) return 0;
    if (!n->left && !n->right) return 1;
    return leaves(n->left) + leaves(n->right);
}
int biggest(Node* n) {
    if (!n) return -2147483647 - 1;
    return max(n->value, max(biggest(n->left), biggest(n->right)));
}

int main() {
    string line;
    getline(cin, line);
    Node* root = buildTree(line);
    cout << "Nodes: " << countNodes(root) << endl;
    cout << "Leaves: " << leaves(root) << endl;
    cout << "Max: " << biggest(root) << endl;
    return 0;
}

Output

Answer