Challenge: Level by Level

Lab C++ Intermediate 20 points

Print the tree one level per line, values left to right separated by spaces, using a queue.

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 line per level.

Example

Input

1 2 3 4 5 N 6

Output

1
2 3
4 5 6

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

Start with the root in the queue.

At the start of each round, q.size() is the size of the level.

Solution explanation

BFS visits nodes in order of their depth.

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 main() {
    string line;
    getline(cin, line);
    Node* root = buildTree(line);
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            Node* n = q.front();
            q.pop();
            cout << n->value << (i + 1 < size ? " " : "\n");
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
    }
    return 0;
}

Output

Answer