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 p(u):
 if u+1:print(s,u,end=s);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);print(s,u,end=s);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);print(s,u,end=s)
s=''
N=int(input())
T=[0,0]*N
R=set(range(N))
for _ in[0]*N:
 a,b,c=map(int,input().split())
 T[a],T[a+N]=b,c
 R-={b,c}
r=R.pop()
print('Preorder')
p(r)
print('\nInorder')
i(r)
print('\nPostorder')
o(r)
print()

Solution (Python):
def p(u):
 if u+1:print(s,u,end=s);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);print(s,u,end=s);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);print(s,u,end=s)
s=''
N=int(input())
T=[0,0]*N
R=set(range(N))
for _ in[0]*N:
 a,b,c=map(int,input().split())
 T[a],T[a+N]=b,c
 R-={b,c}
r=R.pop()
print('Preorder')
p(r)
print('\nInorder')
i(r)
print('\nPostorder')
o(r)
print()

Solution (Python):
def p(u):
 if u+1:print(s,u,end=s);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);print(s,u,end=s);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);print(s,u,end=s)
s=''
N=int(input())
T=[0,0]*N
for _ in[0]*N:
 a,b,c=map(int,input().split())
 T[a],T[a+N]=b,c
r=(set(range(N))-set(T)).pop()
print('Preorder')
p(r)
print('\nInorder')
i(r)
print('\nPostorder')
o(r)
print()

Solution (Python):
def p(u):
 if u+1:print(s,u,end=s);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);print(s,u,end=s);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);print(s,u,end=s)
s=''
N=int(input())
T=[0,0]*N
for _ in[0]*N:
 a,b,c=map(int,input().split())
 T[a],T[a+N]=b,c
r=(set(range(N))-set(T)).pop()
print('Preorder')
p(r)
print('\nInorder')
i(r)
print('\nPostorder')
o(r)
print()

Solution (Python):
def p(u):
 if u+1:print(s,u,end=s);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);print(s,u,end=s);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);print(s,u,end=s)
s=''
N=int(input())
T=[0,0]*N
for _ in[0]*N:
 a,b,c=map(int,input().split())
 T[a],T[a+N]=b,c
r=(set(range(N))-set(T)).pop()
print('Preorder');p(r)
print('\nInorder');i(r)
print('\nPostorder');o(r)
print()

Solution (Python):
def p(u):
 if u+1:print(s,u,end=s);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);print(s,u,end=s);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);print(s,u,end=s)
s=''
N=int(input())
Z=[0]*N
T=Z+Z
for _ in Z:
 a,b,c=map(int,input().split())
 T[a],T[a+N]=b,c
r=(set(range(N))-set(T)).pop()
print('Preorder');p(r)
print('\nInorder');i(r)
print('\nPostorder');o(r)
print()

Solution (Python):
def p(u):
 if u+1:print(s,u,end=s);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);print(s,u,end=s);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);print(s,u,end=s)
s=''
N=int(input())
T=[0,0]*N
for _ in[0]*N:
 e=list(map(int,input().split()))
 T[e[0]],T[e[0]+N]=e[1:]
r=(set(range(N))-set(T)).pop()
print('Preorder');p(r)
print('\nInorder');i(r)
print('\nPostorder');o(r)
print()

Solution (Python):
def s(x):print('',x,end='')
def p(u):
 if u+1:s(u);p(T[u]);p(T[u+N])
def i(u):
 if u+1:i(T[u]);s(u);i(T[u+N])
def o(u):
 if u+1:o(T[u]);o(T[u+N]);s(u)
N=int(input())
T=[0,0]*N
for _ in[0]*N:
 a,b,c=map(int,input().split())
 T[a],T[a+N]=b,c
r=(set(range(N))-set(T)).pop()
print('Preorder');p(r)
print('\nInorder');i(r)
print('\nPostorder');o(r)
print()

Solution (Python):

class Tree:
    nodes = []
    def __init__(self):
        self.root = None
    def insert(self, nodenum, leftnum, rightnum):
        if leftnum != -1:
            self.nodes[nodenum].left = self.nodes[leftnum]
            self.nodes[leftnum].parent = self.nodes[nodenum]
        if rightnum != -1:
            self.nodes[nodenum].right = self.nodes[rightnum]
            self.nodes[rightnum].parent = self.nodes[nodenum]
    def preorder_walk(self, node):
        if node == -1:
            return
        print("", node.label, end = "")
        self.preorder_walk(node.left)
        self.preorder_walk(node.right)
    def inorder_walk(self, node):
        if node == -1:
            return
        self.inorder_walk(node.left)
        print("", node.label, end = "")
        self.inorder_walk(node.right)
    def postorder_walk(self, node):
        if node == -1:
            return
        self.postorder_walk(node.left)
        self.postorder_walk(node.right)
        print("", node.label, end = "")

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

tree = Tree()
n = int(input())
for i in range(n):
    tree.nodes.append(Node(i))
for i in range(n):
    num, left, right = map(int, input().split())
    tree.insert(num, left, right)
for i in tree.nodes:
    if i.parent == -1:
        print("Preorder")
        tree.preorder_walk(i)
        print("")
        print("Inorder")
        tree.inorder_walk(i)
        print("")
        print("Postorder")
        tree.postorder_walk(i)
        print("")

Solution (Python):
class BinaryTree:
    class Node:
        def __init__(self, nid, left, right):
            self.id = nid
            self.left = left
            self.right = right

        def has_left(self):
            return self.left is not None

        def has_right(self):
            return self.right is not None

        def __str__(self):
            return str(self.id)

    @classmethod
    def create(cls, ids):
        nodes = [None] * len(ids)

        def _create(nid):
            if nid in nodes:
                return nodes[nid]
            if nid == -1:
                return None

            lid, rid = ids[nid]
            if lid == -1 and rid == -1:
                right = None
                left = None
            elif lid == -1:
                right = _create(rid)
                left = None
            elif lid == -1:
                right = None
                left = _create(lid)
            else:
                right = _create(rid)
                left = _create(lid)
            nodes[nid] = cls.Node(nid, left, right)
            return nodes[nid]

        def _root(nodeids):
            for nid in range(len(nodeids)):
                if all([lid != nid and rid != nid for lid, rid in nodeids]):
                    return nid

        root = _create(_root(ids))
        return cls(root)

    def __init__(self, root):
        self.root = root

    def preorder(self):
        def _preorder(node):
            yield node
            if node.has_left():
                yield from _preorder(node.left)
            if node.has_right():
                yield from _preorder(node.right)
        yield from _preorder(self.root)

    def inorder(self):
        def _inorder(node):
            if node.has_left():
                yield from _inorder(node.left)
            yield node
            if node.has_right():
                yield from _inorder(node.right)
        yield from _inorder(self.root)

    def postorder(self):
        def _postorder(node):
            if node.has_left():
                yield from _postorder(node.left)
            if node.has_right():
                yield from _postorder(node.right)
            yield node
        yield from _postorder(self.root)


def run():
    n = int(input())

    nodeids = [None] * n
    for i in range(n):
        nid, lid, rid = [int(x) for x in input().split()]
        nodeids[nid] = [lid, rid]

    tree = BinaryTree.create(nodeids)

    print('Preorder')
    for node in tree.preorder():
        print(" {}".format(node), end="")
    print()
    print('Inorder')
    for node in tree.inorder():
        print(" {}".format(node), end="")
    print()
    print('Postorder')
    for node in tree.postorder():
        print(" {}".format(node), end="")
    print()


if __name__ == '__main__':
    run()

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

def preorder(ns, i):
    print(" " + str(i), end ="")
    if ns[i].left != -1:
        preorder(ns, ns[i].left)
    if ns[i].right != -1:
        preorder(ns, ns[i].right)

def inorder(ns, i):
    if ns[i].left != -1:
        inorder(ns, ns[i].left)
    print(" " + str(i), end ="")
    if ns[i].right != -1:
        inorder(ns, ns[i].right)

def postorder(ns, i):
    if ns[i].left != -1:
        postorder(ns, ns[i].left)
    if ns[i].right != -1:
        postorder(ns, ns[i].right)
    print(" " + str(i), end ="")
    
    
n = int(input())
ns = [Node() for i in range(n)]
for i in range(n):
    p, l, r = map(int, input().split())
    if l != -1:
        ns[p].left = l
        ns[l].parent = p
    if r != -1:
        ns[p].right = r
        ns[r].parent = p

for i in range(n):
    if ns[i].parent == -1:
        print("Preorder")
        preorder(ns, i)
        print()
        print("Inorder")
        inorder(ns, i)
        print()
        print("Postorder")
        postorder(ns, i)
        print()

Solution (Python):
from enum import Enum, auto
from collections import deque

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.sibling = None
        self.color = Color.WHITE

def print_elements(ordered):
    for ele in ordered:
        print(' {}'.format(ele), end='')
    print('')

n = int(input())
nodes = [BinaryTreeNode() for i in range(n)]
for i in range(n):
    id, left, right = list(map(int, input().split(' ')))
    if left != -1:
        nodes[id].left = left
        nodes[left].parent = id
        nodes[left].sibling = right
    if right != -1:
        nodes[id].right = right
        nodes[right].parent = id
        nodes[right].sibling = left

root = 0
for i in range(n):
    if nodes[i].parent == None:
        root = i

def init_color():
    global nodes
    for i in range(len(nodes)):
        nodes[i].color = Color.WHITE

def preorder_bfs(s):
    preordered.append(s)
    nodes[s].color = Color.GRAY
    if nodes[s].left != None and nodes[nodes[s].left].color == Color.WHITE:
        preorder_bfs(nodes[s].left)
    if nodes[s].right != None and nodes[nodes[s].right].color == Color.WHITE:
        preorder_bfs(nodes[s].right)
    nodes[s].color = Color.BLACK

inorder_stack = deque([])
def inorder_dfs_init(s):
    init_color()
    inorder_stack.append(s)
    inorder_dfs()

def inorder_dfs():
    u = inorder_stack.pop()
    if nodes[u].left != None and nodes[nodes[u].left].color == Color.WHITE:
        inorder_stack.append(u)
        inorder_stack.append(nodes[u].left)
        inorder_dfs()
    inordered.append(u)
    if nodes[u].right != None and nodes[nodes[u].right].color == Color.WHITE:
        inorder_stack.append(nodes[u].right)
        inorder_dfs()

postorder_stack = deque([])
def postorder_dfs_init(s):
    init_color()
    postorder_stack.append(s)
    postorder_dfs()

def postorder_dfs():
    u = postorder_stack.pop()
    if nodes[u].left != None and nodes[nodes[u].left].color == Color.WHITE:
        postorder_stack.append(u)
        postorder_stack.append(nodes[u].left)
        postorder_dfs()
    if nodes[u].right != None and nodes[nodes[u].right].color == Color.WHITE:
        postorder_stack.append(nodes[u].right)
        postorder_dfs()
    postordered.append(u)

print('Preorder') 
preordered = []
preorder_bfs(root)
print_elements(preordered)

print('Inorder') 
inordered = []
inorder_dfs_init(root)
print_elements(inordered)

print('Postorder') 
postordered = []
postorder_dfs_init(root)
print_elements(postordered)

Solution (Python):

"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_B
@author: maezawa
"""

n = int(input())

parent = [-1 for _ in range(n)]
left = [-1 for _ in range(n)]
right = [-1 for _ in range(n)]
height = [None for _ in range(n)]
depth = [None for _ in range(n)]

def set_parent():
    global parent
    for i in range(n):
        if left[i] != -1:
            parent[left[i]] = i
        if right[i] != -1:
            parent[right[i]] = i

    
def set_depth(i, p):
    global depth
    if depth[i] != None:
        return
    depth[i] = p
    if right[i] != None:
        set_depth(right[i], p)
    if left[i] != None:
        set_depth(left[i], p+1)
       
def get_depth(i):
    global depth
    if depth[i] != None:
        return depth[i]
    d = 0
    u = i
    while parent[u] != -1:
        u = parent[u]
        d += 1
    depth[i] = d
    return d

def set_height(u):
    global height
    h1 = 0
    h2 = 0
    if right[u] != -1:
        h1 = set_height(right[u])+1
    if left[u] != -1:
        h2 = set_height(left[u])+1
    height[u] = max(h1, h2)
    return height[u]    

def get_sib(i):
    if right[parent[i]] == i:
        return left[parent[i]]
    else:
        return right[parent[i]]
    
def get_deg(i):
    deg = 0
    if right[i] != -1:
        deg += 1
    if left[i] != -1:
        deg += 1
    return deg    

def get_height(i):
    return height[i]

def preparse(i):
    if i == -1:
        return
    print(' {}'.format(i), end='')
    preparse(left[i])
    preparse(right[i])
    
def inparse(i):
    if i == -1:
        return
    inparse(left[i])
    print(' {}'.format(i), end='')
    inparse(right[i])
 
def postparse(i):
    if i == -1:
        return
    postparse(left[i])
    postparse(right[i])
    print(' {}'.format(i), end='')

for i in range(n):
    line = list(map(int, input().split()))
    left[line[0]] = line[1]
    right[line[0]] = line[2]

set_parent()
root = parent.index(-1)
print('Preorder')
preparse(root)
print()
print('Inorder')
inparse(root)
print()
print('Postorder')
postparse(root)
print()

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


n = int(input())
binary_tree = [Node() for i in range(n)]
pre_lst, in_lst, post_lst = [], [], []


def pre_order(u):
    if u == -1:
        return

    pre_lst.append(u)
    pre_order(binary_tree[u].left)
    pre_order(binary_tree[u].right)


def in_order(u):
    if u == -1:
        return

    in_order(binary_tree[u].left)
    in_lst.append(u)
    in_order(binary_tree[u].right)


def post_order(u):
    if u == -1:
        return

    post_order(binary_tree[u].left)
    post_order(binary_tree[u].right)
    post_lst.append(u)


def main():
    for i in range(n):
        idx, left, right = map(int, input().split())
        binary_tree[idx].left = left
        binary_tree[idx].right = right
        if left != -1:
            binary_tree[left].parent = idx
        if right != -1:
            binary_tree[right].parent = idx

    root_idx = 0
    for i in range(n):
        if binary_tree[i].parent == -1:
            root_idx = i
            break

    pre_order(root_idx)
    in_order(root_idx)
    post_order(root_idx)

    print("Preorder")
    print("", " ".join([str(i) for i in pre_lst]))
    print("Inorder")
    print("", " ".join([str(i) for i in in_lst]))
    print("Postorder")
    print("", " ".join([str(i) for i in post_lst]))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
root = set(range(n))
nodes = [0 for i in range(n)]
for i in range(n):
    node = list(map(int, input().split()))
    children = node[1:3]
    root -= set(children)
    nodes[node[0]] = children

def preorder(id):
    if(id == -1):
        return
    order.append(id)
    preorder(nodes[id][0])
    preorder(nodes[id][1])

def inorder(id):
    if(id == -1):
        return
    inorder(nodes[id][0])
    order.append(id)
    inorder(nodes[id][1])

def postorder(id):
    if(id == -1):
        return
    postorder(nodes[id][0])
    postorder(nodes[id][1])
    order.append(id)

order = []
preorder(list(root)[0])
print('Preorder')
print(' ', end='')
print(*order)
order = []
inorder(list(root)[0])
print('Inorder')
print(' ', end='')
print(*order)
order = []
postorder(list(root)[0])
print('Postorder')
print(' ', end='')
print(*order)

Solution (Python):
class Tree:
    def __init__(self, ary):
        self.nodes = [
            Node(node, self) for node in sorted(ary, key=lambda x: x[0])
        ]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                self.root = node
                break
        self.root.set_depth(0)
        self.root.set_height()

    def output(self):
        [node.output() for node in self.nodes]

    def preorder(self):
        print('Preorder')
        self.root.preorder()
        print()

    def inorder(self):
        print('Inorder')
        self.root.inorder()
        print()

    def postorder(self):
        print('Postorder')
        self.root.postorder()
        print()


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.left = node[1]
        self.right = node[2]
        self.parent = -1
        self.sibling = -1
        self.degree = 0

    def set(self):
        if self.left > -1:
            self.tree.nodes[self.left].parent = self.no
            if self.right > -1:
                self.tree.nodes[self.right].sibling = self.left
            self.degree += 1

        if self.right > -1:
            self.tree.nodes[self.right].parent = self.no
            if self.left > -1:
                self.tree.nodes[self.left].sibling = self.right
            self.degree += 1

    def set_depth(self, d):
        self.depth = d
        if self.left > -1:
            self.tree.nodes[self.left].set_depth(d + 1)
        if self.right > -1:
            self.tree.nodes[self.right].set_depth(d + 1)

    def set_height(self):
        if self.degree == 0:
            self.height = 0
        else:
            self.tree.nodes[self.right].set_height()
            self.tree.nodes[self.left].set_height()
            self.height = 1 + max(self.tree.nodes[self.right].height,
                                  self.tree.nodes[self.left].height)

    def output(self):
        if self.parent == -1:
            kind = 'root'
        elif self.degree == 0:
            kind = 'leaf'
        else:
            kind = 'internal node'
        print(
            'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.
            format(self.no, self.parent, self.sibling, self.degree, self.depth,
                   self.height, kind))

    def preorder(self):
        print(' {}'.format(self.no), end='')
        if self.left > -1:
            self.tree.nodes[self.left].preorder()
        if self.right > -1:
            self.tree.nodes[self.right].preorder()

    def inorder(self):
        if self.left > -1:
            self.tree.nodes[self.left].inorder()
        print(' {}'.format(self.no), end='')
        if self.right > -1:
            self.tree.nodes[self.right].inorder()

    def postorder(self):
        if self.left > -1:
            self.tree.nodes[self.left].postorder()
        if self.right > -1:
            self.tree.nodes[self.right].postorder()
        print(' {}'.format(self.no), end='')


n = int(input())
ary = [[int(_) for _ in input().split()] for i in range(n)]
tree = Tree(ary)
tree.preorder()
tree.inorder()
tree.postorder()

Solution (Python):
class NullNode():
    def __init__(self):
        self.id = -1

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

def preorder(node, out_list=[]):
    if node.id != -1:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id != -1:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def postorder(node, out_list=[]):
    if node.id != -1:
        out_list = postorder(node.left, out_list)
        out_list = postorder(node.right, out_list)
        out_list.append(str(node.id))
    return out_list

n = int(input())
node_list = [Node(id) for id in range(n)]
for i in range(n):
    [id, left, right] = [int(j) for j in input().split()]
    i_node = node_list[id]
    if left != -1:
        i_node.left = node_list[left]
        node_list[left].parent = node_list[id]
    if right != -1:
        i_node.right = node_list[right]
        node_list[right].parent = node_list[id]

for node in node_list:
    if node.parent.id == -1:
        root = node

print('Preorder')
out_list = preorder(root)
print(' ' + ' '.join(out_list))

print('Inorder')
out_list = inorder(root)
print(' ' + ' '.join(out_list))

print('Postorder')
out_list = postorder(root)
print(' ' + ' '.join(out_list))

Solution (Python):
def preorder(tree, now):
    if now == -1:
        return []
    else:
        left = tree[now][0]
        right = tree[now][1]
        return [now] + preorder(tree, left) + preorder(tree, right)


def inorder(tree, now):
    if now == -1:
        return []
    else:
        left = tree[now][0]
        right = tree[now][1]
        return inorder(tree, left) + [now] + inorder(tree, right)


def postorder(tree, now):
    if now == -1:
        return []
    else:
        left = tree[now][0]
        right = tree[now][1]
        return postorder(tree, left) + postorder(tree, right) + [now]


def print_list_split_whitespace(a):
    print(" ", end="")
    for x in a[:-1]:
        print(x, end=" ")
    print(a[-1])


n = int(input())
tree = [[] for _ in range(n)]
ps = [-1 for _ in range(n)]
ss = [-1 for _ in range(n)]
for _ in range(n):
    s = input().split()
    id = int(s[0])
    left = int(s[1])
    right = int(s[2])
    tree[id] = [left, right]
    if left >= 0:
        ps[left] = id
        ss[left] = right
    if right >= 0:
        ps[right] = id
        ss[right] = left

root = ps.index(-1)

print("Preorder")
pre_list = preorder(tree, root)
print_list_split_whitespace(pre_list)

print("Inorder")
in_list = inorder(tree, root)
print_list_split_whitespace(in_list)

print("Postorder")
post_list = postorder(tree, root)
print_list_split_whitespace(post_list)

Solution (Python):
n = int(input())
tree = [[-1, -1, True] for i in range(n)]
for i in range(n):
    id, left, right = map(int, input().split())
    if left != -1:
        tree[id][0] = left
        tree[left][2] = False
    if right != -1:
        tree[id][1] = right
        tree[right][2] = False

def preoder(id):
    if id == -1:
        return
    print(' ' + str(id), end='')
    preoder(tree[id][0])
    preoder(tree[id][1])

def inorder(id):
    if id == -1:
        return
    inorder(tree[id][0])
    print(' ' + str(id), end='')
    inorder(tree[id][1])

def postorder(id):
    if id == -1:
        return
    postorder(tree[id][0])
    postorder(tree[id][1])
    print(' ' + str(id), end='')

root = 0
for i, node in enumerate(tree):
    if node[2] == True:
        root = i

print('Preorder')
preoder(root)
print('')
print('Inorder')
inorder(root)
print('')
print('Postorder')
postorder(root)
print('')

Solution (Python):

N = int(input())
T = []
class Tree:
    def __init__(self,ID,l=None,r=None,p=-1):
        self.ID = ID
        self.l = l
        self.r = r
        self.p = p

    def makeTree(self):
        for i in range(N):
            T.append(Tree(i))


def preParse(tree):
    if tree == None:
        return
    else:
        ID = tree.ID
        global preList
        preList.append(ID)
        preParse(tree.l)
        preParse(tree.r)
        
def inParse(tree):
    if tree == None:
        return
    else:
        ID = tree.ID
        global inList
        inParse(tree.l)
        inList.append(ID)
        inParse(tree.r)

def posParse(tree):
    if tree == None:
        return
    else:
        ID = tree.ID
        global posList
        posParse(tree.l)
        posParse(tree.r)
        posList.append(ID)
        
    
trees = [list(map(int,input().split())) for i in range(N)]
Tree.makeTree(Tree)
for i in range(N):
    ID,l,r = trees[i]
    tree = T[ID]
    if l != -1:
        T[l].p = tree
        tree.l = T[l]
    if r != -1:
        T[r].p = tree
        tree.r = T[r]
    
for i in range(N):
    if T[i].p == -1:
        parent = T[i]

preList = []
inList = []
posList = []
preParse(parent)
inParse(parent)
posParse(parent)

def convert(List, order):
    a =  " " + " ".join([str(num) for num in List])
    print("{}".format(order))
    print(a)
convert(preList, "Preorder")
convert(inList, "Inorder")
convert(posList, "Postorder")

Solution (Python):
Parent = 0
Lchild = 1
Rchild = 2

def childs(n):
    return node[n][Lchild:Rchild+1]

def preorder(n):
    if n == -1: return []
    c1, c2 = childs(n)
    return [n] + preorder(c1) + preorder(c2)

def inorder(n):
    if n == -1: return []
    c1, c2 = childs(n)
    return inorder(c1) + [n] +inorder(c2)

def postorder(n):
    if n == -1: return []
    c1, c2 = childs(n)
    return postorder(c1) + postorder(c2) + [n]

n = int(input())
node = [[-1, -1, -1] for i in range(n)]
for i in range(n):
    j, e1, e2 = map(int, raw_input().split())
    if e1 != -1:
        node[j][Lchild] = e1
        node[e1][Parent] = j
    if e2 != -1:
        node[j][Rchild] = e2
        node[e2][Parent] = j
for root in range(n):
    if node[root][Parent] == -1: break

print 'Preorder'
print ' ' + ' '.join(map(str, preorder(root)))

print 'Inorder'
print ' ' + ' '.join(map(str, inorder(root)))

print 'Postorder'
print ' ' + ' '.join(map(str, postorder(root)))

Solution (Python):

from __future__ import division, print_function
from sys import stdin


class Node(object):
    def __init__(self):
        self.id = None
        self.parent = -1
        self.childs = None


def preorder_walk(data, index, out):
    node = data[index]
    out.append(node.id)
    for cidx in node.childs:
        if cidx >= 0:
            preorder_walk(data, cidx, out)


def inorder_walk(data, index, out):
    cid = data[index].childs[0]
    if cid >= 0:
        inorder_walk(data, cid, out)
    out.append(data[index].id)
    cid = data[index].childs[1]
    if cid >= 0:
        inorder_walk(data, cid, out)


def postorder_wark(data, index, out):
    node = data[index]
    for cidx in node.childs:
        if cidx >= 0:
            postorder_wark(data, cidx, out)
    out.append(node.id)


n = int(stdin.readline())

data = [Node() for _ in range(n)]
for _ in range(n):
    idx, left, right = (int(s) for s in stdin.readline().split())
    data[idx].id = idx
    data[idx].childs = [left, right]
    for c in data[idx].childs:
        if c >= 0:
            data[c].parent = idx

start = None
for node in data:
    if node.parent == -1:
        start = node.id
        break

for name, func in (('Preorder\n', preorder_walk),
                   ('Inorder\n', inorder_walk),
                   ('Postorder\n', postorder_wark)):
    out = []
    func(data, start, out)
    print(name, *out)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2**20)

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

def Preorder(u):
    if u == -1:
        return
    print(' {}'.format(u), end='')
    Preorder(T[u].left)
    Preorder(T[u].right)
            
def Inorder(u):
    if u == -1:
        return
    Inorder(T[u].left)
    print(' {}'.format(u), end='')
    Inorder(T[u].right)

def Postorder(u):
    if u == -1:
        return
    Postorder(T[u].left)
    Postorder(T[u].right)
    print(' {}'.format(u), end='')

n = int(input())
T = [None] * n
for i in range(n):
    temp = Node()
    T[i] = temp

for i in range(n):
    d = 0
    L = [int(x) for x in input().split()]
    v, l, r = L[0], L[1], L[2]
    T[v].id = v
    T[v].left = l
    T[v].right = r
    if l != -1:
        T[l].p = v
    if r != -1:
        T[r].p = v

for i, t in enumerate(T):
    if t.p == None:
        t.p = -1
        root = i

print('Preorder')
Preorder(T[root].id)
print('\nInorder')
Inorder(T[root].id)
print('\nPostorder')
Postorder(T[root].id)
print('')

Solution (Python):
def pre(k):
    global nodes

    print(' ' + str(k), end= '')

    if nodes[k][1] != -1:
        pre(nodes[k][1])

    if nodes[k][2] != -1:
        pre(nodes[k][2])

def ino(k):
    global nodes

    if nodes[k][1] != -1:
        ino(nodes[k][1])

    print(' ' + str(k), end= '')

    if nodes[k][2] != -1:
        ino(nodes[k][2])
    


def pos(k):
    global nodes

    if nodes[k][1] != -1:
        pos(nodes[k][1])

    if nodes[k][2] != -1:
        pos(nodes[k][2])


    print(' ' + str(k), end= '')



n = int(input())
nodes = []

for i in range(n):
    nodes.append([-1])


for i in range(n):
    a = list(map(int, input().split()))
    if a[1] != -1:
        nodes[a[1]][0] = a[0]
    if a[2] != -1:
        nodes[a[2]][0] = a[0]
    
    nodes[a[0]] += a[1:]

for i in range(len(nodes)):
    if nodes[i][0] == -1:
        ro = i
        break

print('Preorder')
pre(ro)
print()
print('Inorder')
ino(ro)
print()
print('Postorder')
pos(ro)
print()