#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
 
enum TNodeType {ntRoot, ntInternal, ntLeaf};
template<typename T>
class TTree;
 
template<typename T>
class TNode
{
    const T FValue;
    TNode* FParent;
    TNode* FLeft;
    TNode* FRight;

public:
    TNode(const T& Value)
     : FValue(Value)
    {
        FParent = NULL;
        FLeft   = NULL;
        FRight  = NULL;
    }
    T Value()const
    {
        return FValue;
    }
    void AddNode(TNode* Node)
    {
        Node->FParent = this;
        if(FValue < Node->FValue){
            assert(FRight);
            FRight = Node;
        }else{
            assert(FLeft);
            FLeft  = Node;
        }
    }
    void SetLeft(TNode* Node)
    {
        Node->FParent = this;
        FLeft = Node;
    }
    void SetRight(TNode* Node)
    {
        Node->FParent = this;
        FRight = Node;
    }
    TNode* CreateLeft(const T& Value)
    {
        assert(FLeft == NULL);
        SetLeft(new TNode(Value));
        return FLeft;
    }
    TNode* CreateRight(const T& Value)
    {
        assert(FRight == NULL);
        SetRight(new TNode(Value));
        return FRight;
    }
    const TNode* Parent()const
    {
        return FParent;
    }
    const TNode* Left()const
    {
        return FLeft;
    }
    const TNode* Right()const
    {
        return FRight;
    }
    const TNode* Find(const T& Value)const
    {
        // std::cout << "Find(" << Value << ")" << std::endl;
        if(FValue == Value) return this;
        TNode* Node = FValue < Value ? FRight : FLeft;
        if(Node) return Node->Find(Value);
        return NULL;
    }
    TNode* Find(const T& Value)
    {
        return const_cast<TNode*>(const_cast<const TNode*>(this)->Find(Value));
    }
};

template<typename T>
int GetNodeDepth(const TNode<T>* Node)
{
    assert(Node);
    int Depth = 0;
    while(Node->Parent()){
        Node = Node->Parent();
        Depth++;
    }
    return Depth;
}
 
template<typename T>
TNodeType GetNodeType(const TNode<T>* Node)
{
    assert(Node);
    if(Node->Parent() == NULL) return ntRoot;
    if(Node->Left() || Node->Right()) return ntInternal;
    return ntLeaf;
}
std::string GetNodeTypeText(const TNodeType& Type)
{
    switch(Type){
    case ntRoot:     return "root";
    case ntInternal: return "internal node";
    case ntLeaf:     return "leaf";
    }
    assert(false);
    return "";
}
 
template<typename T>
const TNode<T>* GetSibling(const TNode<T>* Node)
{
    assert(Node);
    const TNode<T>* Parent = Node->Parent();
    if(Parent == NULL) return NULL;
    if(Parent->Left()  && Parent->Left()  != Node) return Parent->Left();
    if(Parent->Right() && Parent->Right() != Node) return Parent->Right();
    return NULL;
}
template<typename T>
const TNode<T>* GetRoot(const TNode<T>* Node)
{
    if(Node->Parent()) return GetRoot(Node->Parent());
    return Node;
}
template<typename T>
int GetDegree(const TNode<T>* Node)
{
    return (Node->Left() ? 1 : 0) + (Node->Right() ? 1 : 0);
}

template<typename T>
int GetHeight(const TNode<T>* Node)
{
    if(Node == NULL) return -1;
    return 1 + std::max(GetHeight(Node->Left()), GetHeight(Node->Right()));
}
template<typename T>
void PrintNode(const TNode<T>* Node)
{
    assert(Node);
// node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root    
    std::cout << 
    "node "       << Node->Value() <<
    ": parent = " << (Node->Parent() ? Node->Parent()->Value() : -1) <<
    ", sibling = "<< (GetSibling(Node) ? GetSibling(Node)->Value() : -1) <<
    ", degree = " << GetDegree(Node) <<
    ", depth = "  << GetNodeDepth(Node) <<
    ", height = "  << GetHeight(Node) << 
    ", "          << GetNodeTypeText(GetNodeType(Node)) <<
    std::endl;
}
template<typename T>
void PrintPreorder(const TNode<T>* Node)
{
//  0 1 2 3 4 5 6 7 8
    if(Node == NULL) return;
    std::cout << " " << Node->Value();
    PrintPreorder(Node->Left());
    PrintPreorder(Node->Right());
}
template<typename T>
void PrintInorder(const TNode<T>* Node)
{
//  2 1 3 0 6 5 7 4 8
    if(Node == NULL) return;
    PrintInorder(Node->Left());
    std::cout << " " << Node->Value();
    PrintInorder(Node->Right());
}
template<typename T>
void PrintPostorder(const TNode<T>* Node)
{
//  2 3 1 6 7 5 8 4 0
    if(Node == NULL) return;
    PrintPostorder(Node->Left());
    PrintPostorder(Node->Right());
    std::cout << " " << Node->Value();
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int n;
    std::cin >> n;
    std::vector<TNode<int>*> Table(n, NULL);
    for(int i = 0; i < n; ++i){
        int id;
        int k;
        int left, right;
        std::cin >> id >> left >> right;
        TNode<int>* Node = Table[id];
        if(Node == NULL){
            Node = new TNode<int>(id);
            Table[id] = Node;
        }
        if(left  >= 0){
            if(Table[left]) Node->SetLeft(Table[left]);
            else Table[left] = Node->CreateLeft(left);
        }
        if(right >= 0){
            if(Table[right]) Node->SetRight(Table[right]);
            else Table[right] = Node->CreateRight(right);
        }
    }

    const TNode<int>* Root = GetRoot(Table[0]);
    std::cout << "Preorder" << std::endl;
    PrintPreorder(Root);
    std::cout << "\nInorder" << std::endl;
    PrintInorder(Root);
    std::cout << "\nPostorder" << std::endl;
    PrintPostorder(Root);
    std::cout << std::endl;
    return 0;
}

Measured memory_bytes: 3176