#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>

using namespace std;

class Node {
public:
    void print() {
        cout << "node " << id_ << ": parent = ";
        printParent();
        cout << ", sibling = " << getSibling() << ", degree = " << getDegree() << ", depth = " << depth_
            << ", height = " << height_ << ", " << type_ << endl;
    }
    static void setup() {
        nodes_ = new Node[25];
    }
    static Node* create(int id, int leftChild, int rightChild) {
        Node* node = nodes_ + id;
        node->setId(id);
        if (leftChild != -1) {
            Node* left = nodes_ + leftChild;
            node->setLeftChild(left);
            left->setParent(node);
        }
        if (rightChild != -1) {
            Node* right = nodes_ + rightChild;
            node->setRightChild(right);
            right->setParent(node);
        }
        return node;
    }
    static Node* getNode(int id) { return  nodes_ + id; }
    static Node* findRoot() {
        Node* node = nodes_;
        while (node->parent_ != nullptr) {
            node = node->parent_;
        }
        return node;
    }
    void setDepth(int depth) {
        depth_ = depth;
        if (leftChild_ != nullptr) {
            leftChild_->setDepth(depth + 1);
        }
        if (rightChild_ != nullptr) {
            rightChild_->setDepth(depth + 1);
        }
    }
    int getDegree() {
        int degree = 0;
        if (leftChild_ != nullptr) {
            ++degree;
        }
        if (rightChild_ != nullptr) {
            ++degree;
        }
        return degree;
    }
    int setHeight() {
        int height = 0;
        if (leftChild_ != nullptr) {
            height = leftChild_->setHeight() + 1;
        }
        if (rightChild_ != nullptr) {
            height = max(height, rightChild_->setHeight() + 1);
        }
        height_ = height;
        return height;
    }
    int getSibling() {
        int sibling = -1;
        if (parent_ != nullptr) {
            Node* node = parent_->rightChild_;
            if (node != nullptr) {
                if (node->id_ != id_) {
                    sibling = node->id_;
                }
            }
            node = parent_->leftChild_;
            if (node != nullptr) {
                if (node->id_ != id_) {
                    sibling = node->id_;
                }
            }
        }
        return sibling;
    }
    void setType() {
        type_ = "root";
        if (rightChild_ != nullptr) {
            rightChild_->setTypeInternalOrLeaf();
        }
        if (leftChild_ != nullptr) {
            leftChild_->setTypeInternalOrLeaf();
        }
    }
    void setTypeInternalOrLeaf() {
        if ((rightChild_ == nullptr) && (leftChild_ == nullptr)) {
            type_ = "leaf";
        }
        else {
            type_ = "internal node";
            if (rightChild_ != nullptr) {
                rightChild_->setTypeInternalOrLeaf();
            }
            if (leftChild_ != nullptr) {
                leftChild_->setTypeInternalOrLeaf();
            }
        }
    }
    void preorderTreeWalk() {
        cout << " " << id_;
        if (leftChild_ != nullptr) {
            leftChild_->preorderTreeWalk();
        }
        if (rightChild_ != nullptr) {
            rightChild_->preorderTreeWalk();
        }
    }
    void inorderTreeWalk() {
        if (leftChild_ != nullptr) {
            leftChild_->inorderTreeWalk();
        }
        cout << " " << id_;
        if (rightChild_ != nullptr) {
            rightChild_->inorderTreeWalk();
        }
    }
    void postorderTreeWalk() {
        if (leftChild_ != nullptr) {
            leftChild_->postorderTreeWalk();
        }
        if (rightChild_ != nullptr) {
            rightChild_->postorderTreeWalk();
        }
        cout << " " << id_;
    }
private:
    Node() : id_(-1), depth_(-1), height_(-1), parent_(nullptr), leftChild_(nullptr), rightChild_(nullptr) {}
    void setId(int id) { id_ = id; }
    void setParent(Node* parent) { parent_ = parent; }
    void setLeftChild(Node* leftChild) { leftChild_ = leftChild; }
    void setRightChild(Node* rightChild) { rightChild_ = rightChild; }
    void printParent() {
        if (parent_ != nullptr) {
            cout << parent_->id_;
        }
        else {
            cout << "-1";
        }
    }

    int id_;
    int depth_;
    int height_;
    Node* parent_;
    Node* leftChild_;
    Node* rightChild_;
    string type_;

    static Node* nodes_;
};

Node* Node::nodes_;

int main()
{
    Node::setup();

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int id, left, right;
        cin >> id >> left >> right;
        assert(id < n);
        Node::create(id, left, right);
    }

    Node* root = Node::findRoot();
    root->setDepth(0);
    root->setHeight();
    root->setType();

    cout << "Preorder" << endl;
    root->preorderTreeWalk();
    cout << endl;

    cout << "Inorder" << endl;
    root->inorderTreeWalk();
    cout << endl;

    cout << "Postorder" << endl;
    root->postorderTreeWalk();
    cout << endl;

}



Measured memory_bytes: 3224