#include <bits/stdc++.h>
using namespace std;

struct node
{
    int left = -1;
    int right = -1;
    int sibling = -1;
    int degree;
    // int depth;
    // int height;
    int parent = -1;
    string type;   // {root, internal node, leaf}
};

int getLeftmost(vector<node> &, int);
int getRightmost(vector<node> &, int);

void tw_preorder(vector<node> &, int);
void tw_inorder(vector<node> &, int);
void tw_postorder(vector<node> &, int);

// int getHeight(vector<node> &, int, int);

int main(int argc, char const *argv[])
{

    int n = 0;
    cin >> n;

    vector<node> bt(n);

    if (n == 1) {
        int id = 0, l = -1, r = -1;
        cin >> id >> l >> r;
        bt[id].left = -1;
        bt[id].right = -1;
        bt[id].degree = 0;
    } else {
        for (int i = 0; i < n; ++i)
    {
        int id = 0, l = -1, r = -1;
        cin >> id >> l >> r;
        bt[id].left = l;
        bt[id].right = r;

        bt[l].parent = id;
        bt[r].parent = id;

        bt[l].sibling = r;
        bt[r].sibling = l;

        if (l == -1 && r == -1) {
            bt[id].degree = 0;
        } else if (l == -1 || r == -1) {
            bt[id].degree = 1;
        } else {
            bt[id].degree = 2;
        }
    }
    }

    int i_root = 0;
    for (int i = 0; i < n; ++i)
    {
        if (bt[i].parent == -1)
        {
            bt[i].type = "root";
            i_root = i;

        }
        else if (bt[i].degree > 0)
        {
            bt[i].type = "internal node";
        }
        else if (bt[i].degree == 0)
        {
            bt[i].type = "leaf";
        }
    }

    int i_leftmost = getLeftmost(bt, i_root);
    int i_rightmost = getRightmost(bt, i_root);

    // cout << i_root << ", " << i_leftmost << ", " << i_rightmost << endl;

    // return 0;

    cout << "Preorder" << endl;
    tw_preorder(bt, i_root);
    cout << endl;

    cout << "Inorder" << endl;
    tw_inorder(bt, i_root);
    cout << endl;

    cout << "Postorder" << endl;
    tw_postorder(bt, i_root);
    cout << endl;
    
    // int height_bt = getHeight(bt, i_root, 0);

    // for (int i = 0; i < n; ++i)
    // {
    //     cout << "node " << i << ": parent = " << bt[i].parent << ", ";
    //     cout << "sibling = " << bt[i].sibling << ", ";
    //     cout << "degree = " << bt[i].degree << ", ";
    //     cout << "depth = " << bt[i].depth << ", ";
    //     cout << "height = " << bt[i].height << ", ";
    //     cout << bt[i].type << endl;
    // }

    return 0;
}

// int getHeight(vector<node> &bt, int id, int dep) {
//     int res = 0;

//     if (id == -1) {
//         return res;
//     } else {
//         bt[id].depth = dep;

//         if (bt.size() == 1 || bt[id].type == "leaf") {
//             ;
//         } else {
//                 res = max(getHeight(bt, bt[id].left, dep + 1), getHeight(bt, bt[id].right, dep + 1)) + 1;
//         }
//     }    

//     bt[id].height = res;

//     return res;
// }

int getLeftmost(vector<node> &bt, int id) {
    int l = bt[id].left;
    if (l == -1) {
        return id;
    } else {
        return getLeftmost(bt, l);
    }
}

int getRightmost(vector<node> &bt, int id) {
    int r = bt[id].right;
    if (r == -1) {
        return id;
    } else {
        return getRightmost(bt, r);
    }
}

void tw_preorder(vector<node> &bt, int id) {
    cout << " " << id;

    int l = bt[id].left;
    if (l != -1) {
        tw_preorder(bt, l);
    }

    int r = bt[id].right;
    if (r != -1) {
        tw_preorder(bt, r);
    }
}

void tw_inorder(vector<node> &bt, int id) {
    int l = bt[id].left;
    if (l != -1) {
        tw_inorder(bt, l);
    }

    cout << " " << id;

    int r = bt[id].right;
    if (r != -1) {
        tw_inorder(bt, r);
    }
}

void tw_postorder(vector<node> &bt, int id) {
    int l = bt[id].left;
    if (l != -1) {
        tw_postorder(bt, l);
    }

    int r = bt[id].right;
    if (r != -1) {
        tw_postorder(bt, r);
    }

    cout << " " << id;
}


Measured memory_bytes: 3188