Problem:
Tree Walk Binary trees are defined recursively. A binary tree T is a structure defined on a finite set of nodes that either  contains no nodes, or  is composed of three disjoint sets of nodes: - a root node. - a binary tree called its left subtree. - a binary tree called its right subtree.   Your task is to write a program which perform tree walks (systematically traverse all nodes in a tree) based on the following algorithms:  Print the root, the left subtree and right subtree (preorder).  Print the left subtree, the root and right subtree (inorder).  Print the left subtree, right subtree and the root (postorder).  Here, the given binary tree consists of n nodes and evey node has a unique ID from 0 to n -1. Input The first line of the input includes an integer n , the number of nodes of the tree. In the next n linen, the information of each node is given in the following format:  id left right   id is the node ID, left is ID of the left child and right is ID of the right child. If the node does not have the left (right) child, the left ( right ) is indicated by -1  Output In the 1st line, print " Preorder ", and in the 2nd line print a list of node IDs obtained by the preorder tree walk. In the 3rd line, print " Inorder ", and in the 4th line print a list of node IDs obtained by the inorder tree walk. In the 5th line, print " Postorder ", and in the 6th line print a list of node IDs obtained by the postorder tree walk. Print a space character before each node ID. Constraints  1 ≤ n ≤ 25  Sample Input 1 9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1 Sample Output 1 Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0   Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
def preParse(u, p):
    if u == -1:
        return p
    p += [u]
    preParse(left[u], p)
    preParse(right[u], p)

def inParse(u, p):
    if u == -1:
        return p
    inParse(left[u], p)
    p += [u]
    inParse(right[u], p)

def postParse(u, p):
    if u == -1:
        return p
    postParse(left[u], p)
    postParse(right[u], p)
    p += [u]

n = int(input())
parent = [-1] * n
left   = [-1] * n
right  = [-1] * n
preo = []
ino  = []
post = []

for i in range(n):
    p, l, r = map(int, input().split())
    left[p] = l
    right[p] = r
    if l != -1:
        parent[l] = p
    if r != -1:
        parent[r] = p

root = parent.index(-1)

preParse(root, preo)
inParse(root, ino)
postParse(root, post)

for i, j in zip(['Preorder', 'Inorder', 'Postorder'], [preo, ino, post]):
    print(i)
    print(' '+' '.join(map(str, j)))

Solution (Python):
class Tree():
    def __init__(self):
        self.nodes = {}
        self.root = None
        self.nodes[-1] = None

    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)

    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id], self.nodes[right_id])

    def set_root(self):
        for id in self.nodes:
            if id == -1:
                continue
            if self.nodes[id].parent is None:
                self.root = self.nodes[id]


class Node():
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.right = None
        self.left = None

    def add_child(self, left, right):
        self.left = left
        self.right = right
        
        for c in [left, right]:
            if c:
                c.parent = self

    def pre_walk(self, ans):
        ans.append(self.id)
        if self.left:
            self.left.pre_walk(ans)
        if self.right:
            self.right.pre_walk(ans)

    def in_walk(self, ans):
        if self.left:
            self.left.in_walk(ans)
        ans.append(self.id)
        if self.right:
            self.right.in_walk(ans)

    def post_walk(self, ans):
        if self is None:
            pass
        else:
            if self.left:
                self.left.post_walk(ans)
            if self.right:
                self.right.post_walk(ans)
            ans.append(self.id)


n = int(input())
tree = Tree()
for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp[0]
    left, right = tmp[1:]
    tree.add_node(id)
    tree.add_child(id, left, right)

tree.set_root()
for i in range(3):
    ans = []
    if i == 0:
        print('Preorder')
        tree.root.pre_walk(ans)
    if i == 1:
        print('Inorder')
        tree.root.in_walk(ans)
    if i == 2:
        print('Postorder')
        tree.root.post_walk(ans)

    print('', *ans)

Solution (Python):
class Node:
    def __init__(self):
        self.id = -1
        self.parent = None
        self.childs = [None, None]
        self.sibling = -1
        self.depth = -1
        self.height = -1

    def parentId(self):
        return -1 if self.parent == None else self.parent.id


n = int(input())
nodes = [Node() for _ in range(n)]

for i in range(n):
    id, l, r = map(int, input().split())
    p = nodes[id]
    p.id = id
    if l >= 0:
        nodes[l].parent = p
        p.childs[0] = nodes[l]
    if r >= 0:
        nodes[r].parent = p
        p.childs[1] = nodes[r]

root = None
for node in nodes:
    if node.parent == None:
        root = node
        break


def preorder(p):
    s = ""
    if p == None:
        return ""
    s += f"{p.id} "
    s += preorder(p.childs[0])
    s += preorder(p.childs[1])
    return s


def inorder(p):
    s = ""
    if p == None:
        return ""
    s += inorder(p.childs[0])
    s += f"{p.id} "
    s += inorder(p.childs[1])
    return s


def postorder(p):
    s = ""
    if p == None:
        return ""
    s += postorder(p.childs[0])
    s += postorder(p.childs[1])
    s += f"{p.id} "
    return s


print("Preorder")
print(" "+preorder(root).strip())
print("Inorder")
print(" "+inorder(root).strip())
print("Postorder")
print(" "+postorder(root).strip())

Solution (Python):
n = int(input())
nodes = []
ref = [0] * n
for i in range(n):
    l = [int(i) for i in input().split()]
    if l[1] != -1:
        ref[l[1]] += 1
    if l[2] != -1:
        ref[l[2]] += 1
    nodes.append(l)

nodes = sorted(nodes, key=lambda x: x[0])

preorder_ans = []
inorder_ans = []
postorder_ans = []



def preorder(u):
    preorder_ans.append(u[0])
    if u[1] != -1:
        preorder(nodes[u[1]])

    if u[2] != -1:
        preorder(nodes[u[2]])


def inorder(u):
    if u[1] != -1:
        inorder(nodes[u[1]])

    inorder_ans.append(u[0])

    if u[2] != -1:
        inorder(nodes[u[2]])


def postorder(u):
    if u[1] != -1:
        postorder(nodes[u[1]])

    if u[2] != -1:
        postorder(nodes[u[2]])

    postorder_ans.append(u[0])


def format_print(l):
    print("", " ".join([str(i) for i in l]))




preorder(nodes[ref.index(0)])
inorder(nodes[ref.index(0)])
postorder(nodes[ref.index(0)])

print("Preorder")
format_print(preorder_ans)
print("Inorder")
format_print(inorder_ans)
print("Postorder")
format_print(postorder_ans)

Solution (Python):

import queue
 
class Node:
    def __init__(self, myNum, left, right):
        self.myNum = myNum
        self.left = left
        self.right = right
        self.parent = -1
        self.bs = -1
        self.nodeType = ""
        self.degree = -1
        self.depth = -1
        self.height = -1
 
         
nodes = []
n = int(input().rstrip())
for i in range(n):
    line = [int(j) for j in input().rstrip().split()]
    nodes.append(Node(line[0],line[1],line[2]))
 
nodes = sorted(nodes, key = lambda x: x.myNum)
 

for node in nodes:
    dg = 0
    if node.left != -1:
        nodes[node.left].parent = node.myNum
        dg += 1
    if node.right != -1:
        nodes[node.right].parent = node.myNum
        dg += 1
    node.degree = dg
 

for node in nodes:
    if node.left != -1 and node.right != -1:
        nodes[node.left].bs = nodes[node.right].myNum
        nodes[node.right].bs = nodes[node.left].myNum
 

for node in nodes:
    if node.parent == -1:
        node.nodeType = "root"
        node.depth = 0
        rootNum = node.myNum
    elif node.left == -1 and node.right == -1:
        node.nodeType = "leaf"
    else:
        node.nodeType = "internal node"
 

q = queue.Queue()
q.put(nodes[rootNum])
while not q.empty():
    nd = q.get()
    if nd.left != -1:
        nodes[nd.left].depth = nd.depth + 1
        q.put(nodes[nd.left])
    if nd.right != -1:
        nodes[nd.right].depth = nd.depth + 1
        q.put(nodes[nd.right])
 

for node in nodes:
    if node.parent == -1 or node.nodeType == "leaf":
        node.height = 0
        q.put(node)
while not q.empty():
    nd = q.get()
    if nd.parent != -1:
        nodes[nd.parent].height = max(nodes[nd.parent].height, nd.height + 1)
        q.put(nodes[nd.parent])


def dfsPreorder(x):
    if nodes[x].height == 0:
        print(" " + str(x),end="")
        return
    
    print(" " + str(nodes[x].myNum),end="")
    if nodes[x].left != -1:
        dfsPreorder(nodes[x].left)
    if nodes[x].right != -1:
        dfsPreorder(nodes[x].right)


def dfsInorder(x):
    if nodes[x].height == 0:
        print(" " + str(x),end="")
        return
    
    if nodes[x].left != -1:
        dfsInorder(nodes[x].left)
    print(" " + str(nodes[x].myNum),end="")
    if nodes[x].right != -1:
        dfsInorder(nodes[x].right)
    

def dfsPostorder(x):
    if nodes[x].height == 0:
        print(" " + str(x),end="")
        return
    
    if nodes[x].left != -1:
        dfsPostorder(nodes[x].left)
    if nodes[x].right != -1:
        dfsPostorder(nodes[x].right)
    print(" " + str(nodes[x].myNum),end="")

print("Preorder")
dfsPreorder(rootNum)
print()
print("Inorder")
dfsInorder(rootNum)
print()
print("Postorder")
dfsPostorder(rootNum)
print()

Solution (Python):

"""
Created on Sat Feb 23 19:42:05 2019

@author: Yamazaki Kenichi
"""

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

tree = [[-1,-1,-1] for i in range(N)]
for i in range(N):
    tree[A[i][0]][1],tree[A[i][0]][2] = A[i][1],A[i][2]
    if A[i][1] != -1:
        tree[A[i][1]][0] = A[i][0]
    if A[i][2] != -1:
        tree[A[i][2]][0] = A[i][0]

def parent(u):
    return tree[u][0]
def lchild(u):
    return tree[u][1]
def rchild(u):
    return tree[u][2]
def depth(u):
    res = 0
    while parent(u) != -1:
        res += 1
        u = parent(u)
    return res
H = [-1 for i in range(N)]
def h(u):
    hl = h(lchild(u)) +1 if lchild(u) != -1 else 0
    hr = h(rchild(u)) +1 if rchild(u) != -1 else 0
    H[u] = max(hl,hr)
    return max(hl,hr)

for i in range(N):
    if parent(i) == -1:
        k = i
ans_pre = []
def pre(u):
    if u != -1:
        ans_pre.append(u)
    if lchild(u) != -1:
        pre(lchild(u))
    if rchild(u) != -1:
        pre(rchild(u))
pre(k)
ans_ino = []
def ino(u):
    if lchild(u) != -1:
        ino(lchild(u))
    if u != -1:
        ans_ino.append(u)
    if rchild(u) != -1:
        ino(rchild(u))
ino(k)
ans_pos = []
def pos(u):
    if lchild(u) != -1:
        pos(lchild(u))
    if rchild(u) != -1:
        pos(rchild(u))
    if u != -1:
        ans_pos.append(u)
pos(k)
print('Preorder')
print(" "+" ".join(map(str,ans_pre)))
print('Inorder')
print(" "+" ".join(map(str,ans_ino)))
print('Postorder')
print(" "+" ".join(map(str,ans_pos)))

Solution (Python):
from sys import stdin

class Node:
    def __init__(self):
        self.parent = -1
        self.children = [-1, -1]

class Tree:
    def __init__(self, nodes):
        self.nodes = nodes

    def size(self):
        return len(self.nodes)

    def preorder(self, i):
        if i != -1:
            c = self.nodes[i].children
            print(" ", i, sep="", end="")
            self.preorder(c[0])
            self.preorder(c[1])

    def inorder(self, i):
        if i != -1:
            c = self.nodes[i].children
            self.inorder(c[0])
            print(" ", i, sep="", end="")
            self.inorder(c[1])

    def postorder(self, i):
        if i != -1:
            c = self.nodes[i].children
            self.postorder(c[0])
            self.postorder(c[1])
            print(" ", i, sep="", end="")

n = int(stdin.readline().rstrip())
nodes = [Node() for _ in range(n)]
for i in range(n):
    l = [int(x) for x in stdin.readline().rstrip().split()]
    nodes[l[0]].children = l[1:3]
    if l[1] != -1:
        nodes[l[1]].parent = l[0]
    if l[2] != -1:
        nodes[l[2]].parent = l[0]

t = Tree(nodes)

root = [node.parent for node in t.nodes].index(-1)
print("Preorder")
t.preorder(root)
print("\nInorder")
t.inorder(root)
print("\nPostorder")
t.postorder(root)
print()

Solution (Python):
class node:
    parent = None
    depth = 0
    degree = 0
    height = 0

    def __init__(self, no, l, r,sib):
        self.no = no
        self.left = l
        self.right = r
        self.sibling = sib
    
    def setsibdepth(self, nodes, d):
        if self.left is None:
            return
        self.depth = d
        self.left.sibling = self.right
        self.right.sibling = self.left
        self.left.setsibdepth(nodes, d+1)
        self.right.setsibdepth(nodes, d+1)

    def setheight(self, nodes, h):
        if self.left is None:
            return h-1
        return max(self.left.setheight(nodes, h+1), self.right.setheight(nodes, h+1))


def preorder(head, h, A):
    if h.left is None:
        return
    A.append(h.no)
    preorder(head, h.left, A)
    preorder(head, h.right, A)
    if head == h:
        print('', *A)

def inorder(head, h, B):
    if h.left is None:
        return
    inorder(head, h.left, B)
    B.append(h.no)
    inorder(head, h.right, B)
    if head == h:
        print('', *B)

def postorder(head, h, C):
    if h.left is None:
        return
    postorder(head, h.left, C)
    postorder(head, h.right, C)
    C.append(h.no)
    if head == h:
        print('', *C)



NULL = node(-1, None, None, None)
head = None
nodes = []
n = int(input())
for i in range(n):
    temp = node(i, None, None, NULL)
    nodes.append(temp)

for i in range(n):
    temp = list(map(int,input().split()))
    if temp[1] == -1:
        nodes[temp[0]].left = NULL
    else:
        nodes[temp[0]].left = nodes[temp[1]]
        nodes[nodes[temp[0]].left.no].parent = nodes[temp[0]]

    if temp[2] == -1:
        nodes[temp[0]].right = NULL
    else:
        nodes[temp[0]].right = nodes[temp[2]]
        nodes[nodes[temp[0]].right.no].parent = nodes[temp[0]]

    if temp[1] == -1 and temp[2] == -1:
        nodes[temp[0]].degree = 0
    elif temp[1] != -1 and temp[2] != -1:
        nodes[temp[0]].degree = 2
    else:
        nodes[temp[0]].degree = 1

for i in range(n):
    if nodes[i].parent is None:
        head = nodes[i]
        break

head.setsibdepth(nodes, 0)

for i in range(n):
    nodes[i].height = nodes[i].setheight(nodes, 0)

A = []
B = []
C = []
print("Preorder")
preorder(head, head, A)
print("Inorder")
inorder(head, head, B)
print("Postorder")
postorder(head, head, C)

Solution (Python):
def preParse(u):
    if u == NIL:
        return
    print(' {}'.format(u), end='')
    preParse(Left[u])
    preParse(Right[u])


def inParse(u):
    if u == NIL:
        return
    inParse(Left[u])
    print(' {}'.format(u), end='')
    inParse(Right[u])


def postParse(u):
    if u == NIL:
        return
    postParse(Left[u])
    postParse(Right[u])
    print(' {}'.format(u), end='')


NIL = -1
n = int(input())
data = [list(map(int, input().split()))for _ in range(n)]
Parent = [NIL]*n
Right = [None]*n
Left = [None]*n
for i in data:
    Right[i[0]] = i[2]
    Left[i[0]] = i[1]
    if i[2] != NIL:
        Parent[i[2]] = i[0]
    if i[1] != NIL:
        Parent[i[1]] = i[0]
for i in range(n):
    if Parent[i] == NIL:
        root = i
'''
print(root)
print(Parent)
print(Right)
print(Left)
'''
print('Preorder')
preParse(root)
print()
print('Inorder')
inParse(root)
print()
print('Postorder')
postParse(root)
print()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

def tree_walk(node):
    par, sib, deg, dep, hei, l, r = nodes[node]
    preo.append(node)
    if l != -1:
        tree_walk(l)
    ino.append(node)
    if r != -1:
        tree_walk(r)
    posto.append(node)
    return

N = INT()


nodes = [[-1, -1, 0, 0, 0, -1, -1] for i in range(N)]
preo = []
ino = []
posto = []

for i in range(N):
    node, l, r = MAP()
    if l != -1:
        nodes[l][0] = node
        nodes[node][5] = l
    if r != -1:
        nodes[r][0] = node
        nodes[node][6] = r

for i in range(N):
    
    if nodes[i][0] == -1:
        tree_walk(i)

print('Preorder')
print(' ', end='')
print(*preo)
print('Inorder')
print(' ', end='')
print(*ino)
print('Postorder')
print(' ', end='')
print(*posto)

Solution (Python):
class Node:
    def __init__(self,left,right):
        self.parent = None
        self.left = left
        self.right = right
    
    def __repr__(self):
        return str(self.parent) + ' ' + str(self.left) + ' ' + str(self.right)

class Tree:
    def __init__(self,n):
        self.T = [Node(None,None) for i in range(n)]
    
    def insert(self,key,left,right):
        self.T[key].left = left
        self.T[key].right = right
        if right != -1:
            self.T[right].parent = key
        if left != -1:
            self.T[left].parent = key
    
    def beforePrint(self):
        self.root = None
        for i in range(len(self.T)):
            if self.T[i].parent == None:
                self.root = i
                break
        return self.root

    def printAll(self):
        
        root = self.beforePrint()
        
        print("Preorder")
        self.printPreOrder(root)
        print()
        print("Inorder")
        self.printInOrder(root)
        print()
        print("Postorder")
        self.printPostOrder(root)
        print()

    
    def printPreOrder(self,key):
        if key == None or key == -1:
            return
        print('',key,end='')
        self.printPreOrder(self.T[key].left)
        self.printPreOrder(self.T[key].right)
    
    def printInOrder(self,key):
        if key == None or key == -1:
            return
        self.printInOrder(self.T[key].left)
        print('',key,end='')
        self.printInOrder(self.T[key].right)
    
    def printPostOrder(self,key):
        if key == None or key == -1:
            return
        self.printPostOrder(self.T[key].left)
        self.printPostOrder(self.T[key].right)
        print('',key,end='')

    


N = int(input())
T = Tree(N)
for i in range(N):
    Q = list(map(int,input().split()))
    T.insert(Q[0], Q[1], Q[2])
T.printAll()

Solution (Python):
from typing import List


class Node:
    left = -1
    right = -1
    parent = -1


def get_root(nodes: List[int]) -> int:
    for i, node in enumerate(nodes):
        if node.parent == -1:
            return i


def show_preorder(node_id: int)-> None:
    print(f' {node_id}', end='')
    if nodes[node_id].left != -1:
        show_preorder(nodes[node_id].left)
    if nodes[node_id].right != -1:
        show_preorder(nodes[node_id].right)


def show_inorder(node_id: int)-> None:
    left = nodes[node_id].left
    if left != -1:
        show_inorder(left)

    print(f' {node_id}', end='')

    right = nodes[node_id].right
    if right != -1:
        show_inorder(right)


def show_postorder(node_id: int) -> None:
    left = nodes[node_id].left
    if left != -1:
        show_postorder(left)

    right = nodes[node_id].right
    if right != -1:
        show_postorder(right)

    print(f' {node_id}', end='')


N = int(input())
nodes = [Node() for i in range(N)]
for _i in range(N):
    node_id, left, right = map(int, input().split())
    nodes[node_id].left = left
    nodes[node_id].right = right
    if left != -1:
        nodes[left].parent = node_id
    if right != -1:
        nodes[right].parent = node_id
root = get_root(nodes)

print('Preorder')
show_preorder(root)
print()

print('Inorder')
show_inorder(root)
print()

print('Postorder')
show_postorder(root)
print()

Solution (Python):
def preorder(idx):
    if idx == -1:
        return 
    left,right = tree[idx]
    print(' {}'.format(idx), end='')
    preorder(left)
    preorder(right)

def inorder(idx):
    if idx == -1:
        return 
    left,right = tree[idx]
    inorder(left)
    print(' {}'.format(idx),end='')
    inorder(right)

def postorder(idx):
    if idx == -1:
        return
    left,right = tree[idx]
    postorder(left)
    postorder(right)
    print(' {}'.format(idx),end='')

n = int(input())
tree = [None]*n
root = set(range(n))

for _ in range(n):
    idx,left,right = map(int,input().split())
    tree[idx] = (left,right)
    root -= set([left,right])
root_node = root.pop()

print("Preorder")
preorder(root_node)
print()

print("Inorder")
inorder(root_node)
print()

print("Postorder")
postorder(root_node)
print()

Solution (Python):
import sys


class Node:
    def __init__(self):
        self.parent = self.left = self.right = None


n = int(sys.stdin.readline())

nodes = [Node() for _ in range(n)]

for _ in range(n):
    id, left, right = map(int, sys.stdin.readline().split())
    if left != -1:
        nodes[id].left = left
        nodes[left].parent = id
    if right != -1:
        nodes[id].right = right
        nodes[right].parent = id


def preorder(id):
    node = nodes[id]
    yield id
    if node.left is not None:
        yield from preorder(node.left)
    if node.right is not None:
        yield from preorder(node.right)


def inorder(id):
    node = nodes[id]
    if node.left is not None:
        yield from inorder(node.left)
    yield id
    if node.right is not None:
        yield from inorder(node.right)


def postorder(id):
    node = nodes[id]
    if node.left is not None:
        yield from postorder(node.left)
    if node.right is not None:
        yield from postorder(node.right)
    yield id


root_id = next(i for i, node in enumerate(nodes) if node.parent is None)
print('Preorder')
print(' ' + ' '.join(map(str, preorder(root_id))))
print('Inorder')
print(' ' + ' '.join(map(str, inorder(root_id))))
print('Postorder')
print(' ' + ' '.join(map(str, postorder(root_id))))

Solution (Python):
class Node:
    def __init__(self, parent=-1, left=-1, right=-1):
        self.parent = parent
        self.left = left
        self.right = right


def preParse(u):
    """先行順巡回"""
    if u == -1:
        return
    print(" {}".format(u), end="")
    preParse(Nodes[u].left)
    preParse(Nodes[u].right)


def inParse(u):
    """中間順巡回"""
    if u == -1:
        return
    inParse(Nodes[u].left)
    print(" {}".format(u), end="")
    inParse(Nodes[u].right)


def postParse(u):
    """後行順巡回"""
    if u == -1:
        return
    postParse(Nodes[u].left)
    postParse(Nodes[u].right)
    print(" {}".format(u), end="")


n = int(input())
Nodes = []
for i in range(n):
    Nodes.append(Node())

for i in range(n):
    tmp = [int(_) for _ in input().split()]
    Nodes[tmp[0]].left = tmp[1]
    Nodes[tmp[0]].right = tmp[2]
    if tmp[1] != -1:
        Nodes[tmp[1]].parent = tmp[0]
    if tmp[2] != -1:
        Nodes[tmp[2]].parent = tmp[0]





for i in range(n):
    if Nodes[i].parent == -1:
        root = i
        break

print("Preorder")
preParse(root)
print("")
print("Inorder")
inParse(root)
print("")
print("Postorder")
postParse(root)
print("")

Solution (Python):
class node:
    def __init__(self,nodeid):
        self.parent = None
        self.parentid = -1
        self.c_leftid = -1
        self.c_left = None
        self.c_rightid = -1
        self.c_right = None
        self.nodeid = nodeid
        self.type = "root"
    def setLeftChild(self,cn):
        self.c_left = cn
        self.c_leftid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def setRightChild(self,cn):
        self.c_right = cn
        self.c_rightid = cn.nodeid
        cn.parent = self
        cn.parentid = self.nodeid
        cn.setNodeType()
        self.setNodeType()
        return
    def getDepth(self):
        cnt = 0
        t = self
        while True:
            if (t.parentid == -1 ):
                break
            t = t.parent
            cnt = cnt + 1
        return cnt
    def setNodeType(self):
        if (self.getDepth() == 0):
            self.type = "root"
        else:
            if ( self.c_rightid == -1 and self.c_leftid == -1 ):
                self.type = "leaf"
            else:
                self.type = "internal node" 
    def getNodeType(self):
        return self.type
    def getSibling(self):
        if ( self.parentid == -1):
            return -1
        i = self.parent
        if ( i.c_rightid == self.nodeid ):
            return i.c_leftid
        elif ( i.c_leftid == self.nodeid):
            return i.c_rightid
    def getHeight(self):
        lcnt = 0
        rcnt = 0
        if (self.c_leftid == -1  and self.c_rightid == -1 ):
            return 0
        elif (self.c_rightid  == -1):
            lcnt = lcnt + self.c_left.getHeight() + 1
        elif (self.c_leftid  == -1):
            rcnt = rcnt + self.c_right.getHeight() + 1
        else:
            lcnt = lcnt + self.c_left.getHeight() + 1
            rcnt = rcnt + self.c_right.getHeight() + 1
        if (lcnt >= rcnt):
            return lcnt
        else:
            return rcnt
    def getDegree(self):
        cnt = 0
        if (self.c_leftid != -1):
            cnt += 1
        if (self.c_rightid != -1):
            cnt += 1
        return cnt
    def getPreorder(self,r1):
        r1.append(self.nodeid)
        if (self.c_leftid != -1):
            r1 = self.c_left.getPreorder(r1)
        if (self.c_rightid != -1):
            r1 = self.c_right.getPreorder(r1)
        return r1       
    def getInorder(self,r1):
        if (self.c_leftid != -1):
            r1 = self.c_left.getInorder(r1)
        r1.append(self.nodeid)
        if (self.c_rightid != -1):
            r1 = self.c_right.getInorder(r1)
        return r1       
    def getPostorder(self,r1):
        if (self.c_leftid != -1):
            r1 = self.c_left.getPostorder(r1)
        if (self.c_rightid != -1):
            r1 = self.c_right.getPostorder(r1)
        r1.append(self.nodeid)
        return r1       
    def getRoot(self):
        if (self.parentid == -1):
            return self
        return self.parent.getRoot()


    def showNode(self):
        i1 = self.nodeid
        i2 = self.parentid
        i3 = self.getSibling()
        i4 = self.getDegree()
        i5 = self.getDepth()
        i6 = self.getHeight()
        i7 = self.getNodeType()
        print ('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i1,i2,i3,i4,i5,i6,i7))
        return

nl = []
n = int(input())
for i in range(0,n):
    nl.append(node(i))

for i in range(0,n):
    (a,b,c) = map(int,input().split())
    if (b != -1):
        nl[a].setLeftChild(nl[b])
    if (c != -1):
        nl[a].setRightChild(nl[c])

root = nl[0].getRoot()
r1 = []
r2 = []
r3 = []
r1 = root.getPreorder(r1)
r2 = root.getInorder(r2)
r3 = root.getPostorder(r3)

print ("Preorder")
print ('',' '.join(map(str,r1)))
print ("Inorder")
print ('',' '.join(map(str,r2)))
print ("Postorder")
print ('',' '.join(map(str,r3)))

Solution (Python):
class Node:
    def __init__(self, left, right):
        self.left_node_no = left
        self.right_node_no = right


def preorder_tree_walk(nodes, node_no, order):
    if node_no not in nodes:
        return
    order.append(node_no)
    preorder_tree_walk(nodes, nodes[node_no].left_node_no, order)
    preorder_tree_walk(nodes, nodes[node_no].right_node_no, order)
    return


def inorder_tree_walk(nodes, node_no, order):
    if node_no not in nodes:
        return
    inorder_tree_walk(nodes, nodes[node_no].left_node_no, order)
    order.append(node_no)
    inorder_tree_walk(nodes, nodes[node_no].right_node_no, order)
    return

def postorder_tree_walk(nodes, node_no, order):
    if node_no not in nodes:
        return
    postorder_tree_walk(nodes, nodes[node_no].left_node_no, order)
    postorder_tree_walk(nodes, nodes[node_no].right_node_no, order)
    order.append(node_no)
    return

def main():
    n = int(input())
    nodes = {}
    for i in range(n):
        node_no, left, right = [int(x) for x in input().split()]
        nodes[node_no] = Node(left, right)

    children = set([val.left_node_no for val in nodes.values()] + [val.right_node_no for val in nodes.values()])
    root_node_no = list(set(nodes.keys()) - children)[0]

    preorder = []
    preorder_tree_walk(nodes, root_node_no, preorder)
    print("Preorder")
    print(" " + " ".join(map(str, preorder)))

    inorder = []
    inorder_tree_walk(nodes, root_node_no, inorder)
    print("Inorder")
    print(" " + " ".join(map(str, inorder)))

    postorder = []
    postorder_tree_walk(nodes, root_node_no, postorder)
    print("Postorder")
    print(" " + " ".join(map(str, postorder)))
    return


main()

Solution (Python):
class Node:
    def __init__(self,name):
        self.name=name
        self.root=None
        self.left=None
        self.right=None



def Preorder(node,order):
    order.append(node.name)
    try:
        Preorder(node.left,order)
    except:
        pass
    try:
        Preorder(node.right,order)
    except:
        pass

def Inorder(node,order):
    try:
        Inorder(node.left,order)
        order.append(node.name)
    except:
        order.append(node.name)
    
    try:
        Inorder(node.right,order)
    except:
        pass

def Postorder(node,order):
    try:
        Postorder(node.left,order)
    except:
        pass
    try:
        Postorder(node.right,order)
    except:
        pass
    order.append(node.name)





n=int(input())
Tree=[]
for i in range(n):
    Tree.append(Node(i))


for loop in range(n):
    name,left,right=map(int,input().split())
    if(left!=-1):
        Tree[name].left=Tree[left]
        Tree[left].root=Tree[name]
    if(right!=-1):
        Tree[name].right=Tree[right]
        Tree[right].root=Tree[name]



for i in range(n):
    if(Tree[i].root is None):
        root=Tree[i]


p_order=[]
Preorder(root,p_order)

i_order=[]
Inorder(root,i_order)

po_order=[]
Postorder(root,po_order)

print("Preorder")
print("",end=" ")
print(" ".join(list(map(str,p_order))))

print("Inorder")
print("",end=" ")
print(" ".join(list(map(str,i_order))))

print("Postorder")
print("",end=" ")
print(" ".join(list(map(str,po_order))))

Solution (Python):
import sys

def walk_preorder(n):
    c = children[n]
    print(' {}'.format(n), end='')
    if c[0]>=0: walk_preorder(c[0])
    if c[1]>=0: walk_preorder(c[1])

def walk_inorder(n):
    c = children[n]
    if c[0]>=0: walk_inorder(c[0])
    print(' {}'.format(n), end='')
    if c[1]>=0: walk_inorder(c[1])

def walk_postorder(n):
    c = children[n]
    if c[0]>=0: walk_postorder(c[0])
    if c[1]>=0: walk_postorder(c[1])
    print(' {}'.format(n), end='')
    

n = int(sys.stdin.readline())
parent = [-1 for _ in range(n)]
children = [[] for _ in range(n)]
for _ in range(n):
    id, left, right = list(map(int, sys.stdin.readline().split()))
    children[id] = [left, right]
    if left>=0:  parent[left] = id
    if right>=0: parent[right] = id

root=parent.index(-1)
order=[]
print('Preorder')
walk_preorder(root)
print()
print('Inorder')
walk_inorder(root)
print()
print('Postorder')
walk_postorder(root)
print()