Challenge: Tree Height

Lab C++ Beginner 10 points

Print the height of the tree (nodes on the longest root-to-leaf path; an empty tree has height 0).

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

One number.

Example

Input

1 2 3 N 4

Output

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

nullptr has height 0.

height = 1 + max(left height, right height).

Solution explanation

Every node is visited once: 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 height(Node* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }

int main() {
    string line;
    getline(cin, line);
    cout << height(buildTree(line)) << endl;
    return 0;
}

Output

Answer