Challenge: Three Traversals

Lab C++ Beginner 10 points

Print the preorder, inorder and postorder traversals, one per line, values separated by spaces.

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

Three lines.

Example

Input

1 2 3 4 5

Output

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

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

Preorder: node, left, right.

Inorder: left, node, right.

Postorder: left, right, node.

Solution explanation

Same recursion, different place for the current node.

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;
}

void pre(Node* n, vector<int>& out)  { if (!n) return; out.push_back(n->value); pre(n->left, out); pre(n->right, out); }
void in(Node* n, vector<int>& out)   { if (!n) return; in(n->left, out); out.push_back(n->value); in(n->right, out); }
void post(Node* n, vector<int>& out) { if (!n) return; post(n->left, out); post(n->right, out); out.push_back(n->value); }

void print(const vector<int>& v) {
    for (size_t i = 0; i < v.size(); i++) cout << v[i] << (i + 1 < v.size() ? " " : "\n");
}

int main() {
    string line;
    getline(cin, line);
    Node* root = buildTree(line);
    vector<int> a, b, c;
    pre(root, a);
    in(root, b);
    post(root, c);
    print(a);
    print(b);
    print(c);
    return 0;
}

Output

Answer