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):
import sys
sys.setrecursionlimit(2**20)

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

def pre_parse(T: dict, u: int, pre_ls: list):
    if u is None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)
    pre_parse(T, T[u].right, pre_ls)

def in_parse(T: dict, u: int, in_ls: list):
    if u is None:
        return
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)

def post_parse(T: dict, u: int, post_ls: list):
    if u is None:
        return
    post_parse(T, T[u].left, post_ls)
    post_parse(T, T[u].right, post_ls)
    post_ls.append(u)


n = int(input())
T = {key: Node(None, None, None) for key in range(n)}
for _ in range(n):
    tmp = list(map(int, input().split()))
    T[tmp[0]].left = tmp[1] if tmp[1] != -1 else None
    T[tmp[0]].right = tmp[2] if tmp[2] != -1 else None
    if tmp[1] != -1:
        T[tmp[1]].parent = tmp[0]
    if tmp[2] != -1:
        T[tmp[2]].parent = tmp[0]
ROOT = 0
for id, node in T.items():
    if node.parent is None:
        ROOT = id
        break

pre_ls, in_ls, post_ls = [], [], []
pre_parse(T, ROOT, pre_ls)
in_parse(T, ROOT, in_ls)
post_parse(T, ROOT, post_ls)

print("Preorder")
print("", *pre_ls)
print("Inorder")
print("", *in_ls)
print("Postorder")
print("", *post_ls)

Solution (Python):
class Node:
    def __init__(self):
        self.parent = -1
        self.degree = 0
        self.sibling = -1

def make_orderlist(node_id, answer_dic):
    preorder(node_id, answer_dic)
    inorder(node_id, answer_dic)
    postorder(node_id,answer_dic)

def preorder(node_id, answer_dic):
    if node_id == -1:
        return
    answer_dic["Preorder"].append(str(node_id))
    preorder(Tree[node_id].left, answer_dic)
    preorder(Tree[node_id].right, answer_dic)
    
def inorder(node_id, answer_dic):
    if node_id == -1:
        return
    inorder(Tree[node_id].left, answer_dic)
    answer_dic["Inorder"].append(str(node_id))
    inorder(Tree[node_id].right, answer_dic)

def postorder(node_id, answer_dic):
    if node_id == -1:
        return
    postorder(Tree[node_id].left, answer_dic)
    postorder(Tree[node_id].right, answer_dic)
    answer_dic["Postorder"].append(str(node_id))
    

N = int(input())
Tree = [Node() for _ in range(N)]


for _ in range(N):
    
    tree_info = list(map(int, input().split()))
    node_id = tree_info[0]
    left = tree_info[1]
    right = tree_info[2]
    
    Tree[node_id].left = left
    Tree[node_id].right = right
    
    if left != -1:
        Tree[left].parent = node_id
    if right != -1:
        Tree[right].parent = node_id
    if left != -1 and right != -1:
        
        Tree[right].sibling = left
        Tree[left].sibling = right
        

root_id =[i for i,t in enumerate(Tree) if t.parent == -1][0]
answer_dic = {"Preorder":[], "Inorder":[], "Postorder":[]}
make_orderlist(root_id, answer_dic)


for i in answer_dic:    
    print(i)
    print(" "+" ".join(answer_dic[i]))

Solution (Python):
class Node():
    def __init__(self):
        self.parent = -1
        self.left = -1
        self.right = -1
        self.depth = 0
        self.sibling = -1
        self.degree = 0
        self.height = -1
        return

def getAncestor(t, n):
    for i in range(n):
        if t[i].parent == -1:
            return i

def preOrderWolk(t, u, load=[]):
    load.append(u)
    if t[u].left != -1:
        load = preOrderWolk(t, t[u].left, load)
    if t[u].right != -1:
        load = preOrderWolk(t, t[u].right, load)
    return load

def inOrderTreeWalk(t, u, load=[]):
    if t[u].left != -1:
        load = inOrderTreeWalk(t, t[u].left, load)
    load.append(u)
    if t[u].right != -1:
        load = inOrderTreeWalk(t, t[u].right, load)
    return load

def PostOrderTreeWalk(t, u, load=[]):
    if t[u].left != -1:
        load = PostOrderTreeWalk(t, t[u].left, load)
    if t[u].right != -1:
        load = PostOrderTreeWalk(t, t[u].right, load)
    load.append(u)
    return load
    

import sys

n = int(input())
t = []
for _ in range(n):
    t.append(Node())

for i in range(n):
    a = list(map(int, sys.stdin.readline().split()))
    m = a[0]
    t[m].left = a[1]
    t[m].right = a[2]
    if a[1] != -1:
        t[m].degree += 1
        t[a[1]].parent = m
        t[a[1]].sibling = a[2]
    if a[2] != -1:
        t[m].degree += 1
        t[a[2]].parent = m
        t[a[2]].sibling = a[1]

r = getAncestor(t,n)
ptw = preOrderWolk(t, r, [])
itw = inOrderTreeWalk(t, r, [])
post = PostOrderTreeWalk(t, r, [])

print('Preorder')
print('',*ptw)
print('Inorder')
print('',*itw)
print('Postorder')
print('',*post)

Solution (Python):



class Node:
    def __init__(self):
        self.parentId=-1
        self.left=-1
        self.right=-1

def preorder(id):
    global node
    print(" "+str(id),end="")
    if node[id].left != -1:
        preorder(node[id].left)
    if node[id].right != -1:
        preorder(node[id].right)
    
def inorder(id):
    global node
    if node[id].left != -1:
        inorder(node[id].left)
    print(" "+str(id),end="")
    if node[id].right != -1:
        inorder(node[id].right)

def postorder(id):
    global node
    if node[id].left !=-1:
        postorder(node[id].left)
    if node[id].right!=-1:
        postorder(node[id].right)
    print(" "+str(id),end="")

n=int(input())
a=[[int(i)for i in input().split()]for j in range(n)]
node=[Node()for i in range(n)]

for i in a:
    id=i[0]
    left=i[1]
    right=i[2]
    node[id].left=left
    node[id].right=right
    if left != -1:node[left].parentId=id
    if right != -1:node[right].parentId =id

root=-1
for i in range(n):
    if node[i].parentId==-1:
        root=i
        break
print("Preorder")
preorder(root)
print("\nInorder")
inorder(root)
print("\nPostorder")
postorder(root)
print("")

Solution (Python):
class SimpleBinaryTree:
    class Node:
        def __init__(self):
            self.num = -1
            self.parent = -1
            self.right = -1
            self.left = -1
    
    def __init__(self, n):
        self.node_num = n
        self.nodes = []
        for i in range(n):
            node = self.Node()
            self.nodes.append(node)
    
    def load(self, tree_info):
        for i in range(self.node_num):
            self.nodes[i].num = tree_info[i][0]
            self.nodes[i].left = tree_info[i][1]
            self.nodes[i].right = tree_info[i][2]
            if self.nodes[i].left != -1:
                self.nodes[self.nodes[i].left].parent = self.nodes[i].num
            if self.nodes[i].right != -1:
                self.nodes[self.nodes[i].right].parent = self.nodes[i].num

    
    def print_preorder(self, i):
        if self.nodes[i].left == -1 and self.nodes[i].right == -1:
            return [self.nodes[i].num]
        elif self.nodes[i].left == -1:
            return [self.nodes[i].num] + self.print_preorder(self.nodes[i].right)
        elif self.nodes[i].right == -1:
            return [self.nodes[i].num] + self.print_preorder(self.nodes[i].left)
        else:
            return [self.nodes[i].num] + self.print_preorder(self.nodes[i].left) + self.print_preorder(self.nodes[i].right)


    def print_inorder(self, i):
        if self.nodes[i].left == -1 and self.nodes[i].right == -1:
            return [self.nodes[i].num]
        elif self.nodes[i].left == -1:
            return [self.nodes[i].num] + self.print_inorder(self.nodes[i].right)
        elif self.nodes[i].right == -1:

            return  self.print_inorder(self.nodes[i].left) + [self.nodes[i].num]
        else:
            return self.print_inorder(self.nodes[i].left) + [self.nodes[i].num] + self.print_inorder(self.nodes[i].right)


    def print_postorder(self, i):
        if self.nodes[i].left == -1 and self.nodes[i].right == -1:
            return [self.nodes[i].num]
        elif self.nodes[i].left == -1:

            return self.print_postorder(self.nodes[i].right) + [self.nodes[i].num] 
        elif self.nodes[i].right == -1:

            return self.print_postorder(self.nodes[i].left) + [self.nodes[i].num]
        else:
            return self.print_postorder(self.nodes[i].left) + self.print_postorder(self.nodes[i].right) + [self.nodes[i].num]


if __name__ == '__main__':
    n = int(input())
    tree_info = [[None]] * n
    for i in range(n):
        line = list(map(int, input().rstrip().split()))
        tree_info[line[0]] = line
    sbt = SimpleBinaryTree(n)
    sbt.load(tree_info)
    for node in sbt.nodes:
        if node.parent == -1:
            top = node.num
            break
    print('Preorder')
    print(' ' + ' '.join(map(str,sbt.print_preorder(top))).rstrip())
    print('Inorder')
    print(' ' + ' '.join(map(str,sbt.print_inorder(top))).rstrip())
    print('Postorder')
    print(' ' + ' '.join(map(str,sbt.print_postorder(top))).rstrip())

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


class BinaryNode:
    def __init__(self, node, left, right):
        self.node = node
        self.left = left
        self.right = right


class BinaryTree:
    def __init__(self, N):
        self.tree = [-1] * N
        self.parent = [-1] * N

    def insert_node(self, N, node):
        self.tree[N] = node
        if node.left is not None:
            self.parent[node.left] = N
        if node.right is not None:
            self.parent[node.right] = N

    def get_root(self):
        for n in range(len(self.parent)):
            if self.parent[n] == -1:
                return n

    def preorder(self, N):
        ret = [N]
        if self.tree[N].left is not None:
            ret.extend(self.preorder(self.tree[N].left))
        if self.tree[N].right is not None:
            ret.extend(self.preorder(self.tree[N].right))
        return ret

    def inorder(self, N):
        ret = []
        if self.tree[N].left is not None:
            ret.extend(self.inorder(self.tree[N].left))
        ret.append(N)
        if self.tree[N].right is not None:
            ret.extend(self.inorder(self.tree[N].right))
        return ret

    def postorder(self, N):
        ret = []
        if self.tree[N].left is not None:
            ret.extend(self.postorder(self.tree[N].left))
        if self.tree[N].right is not None:
            ret.extend(self.postorder(self.tree[N].right))
        ret.append(N)
        return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    tree = BinaryTree(N)
    for n in range(N):
        n, left, right = il()
        if left == -1: left = None
        if right == -1: right = None
        tree.insert_node(n, BinaryNode(n, left, right))
    print('Preorder')
    print('', *tree.preorder(tree.get_root()))
    print('Inorder')
    print('', *tree.inorder(tree.get_root()))
    print('Postorder')
    print('', *tree.postorder(tree.get_root()))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

class Node:
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.left = None
        self.right = None
        self.depth = 0
    
    def get_depth(self):
        if not self.parent:
            return 0
        else:
            return self.parent.get_depth()+1
    
    def get_sibling(self):
        if not self.parent:
            return - 1
        else:
            if self.parent.right and self.parent.right.val == self.val:
                if self.parent.left:
                    return self.parent.left.val
                else:
                    return - 1
            elif self.parent.left and self.parent.left.val == self.val:
                if self.parent.right:
                    return self.parent.right.val
                else:
                    return - 1
    
    def get_parent(self):
        if not self.parent:
            return -1
        return self.parent.val
    
    def get_degree(self):
        degree = 0
        if self.left:
            degree += 1
        if self.right:
            degree += 1
        return degree
    
    def get_type(self):
        if not self.parent:
            return "root"
        elif self.left or self.right:
            return "internal node"
        else:
            return "leaf"
    
    def get_height(self):
        if not self.left and not self.right:
            return 0
        l,r = 0,0
        if self.left:
            l = self.left.get_height()
        if self.right:
            r = self.right.get_height()
        return max(l + 1,r + 1)


def main():
    n = int(input().strip())
    nodes = [Node(i) for i in range(n)]

    
    for _ in range(n):
        val, left, right = [int(i) for i in input().strip().split()]
        if left != -1:
            nodes[val].left,nodes[left].parent = nodes[left],nodes[val]
        if right != -1:
            nodes[val].right,nodes[right].parent = nodes[right],nodes[val]

    
    depth = [node.get_depth() for node in nodes]
    root = nodes[depth.index(0)]

    
    preorder = []

    def preorder_walk(node):
        preorder.append(str(node.val))
        if node.left:
            preorder_walk(node.left)
        if node.right:
            preorder_walk(node.right)

    

    inorder = []

    def inorder_walk(node):
        if node.left:
            inorder_walk(node.left)
        inorder.append(str(node.val))
        if node.right:
            inorder_walk(node.right)

    

    postorder = []

    def postorder_walk(node):
        if node.left:
            postorder_walk(node.left)
        if node.right:
            postorder_walk(node.right)
        postorder.append(str(node.val))

    preorder_walk(root)
    inorder_walk(root)
    postorder_walk(root)

    print("Preorder")
    print(""," ".join(preorder))
    print("Inorder")
    print(""," ".join(inorder))
    print("Postorder")
    print(""," ".join(postorder))


if __name__ == "__main__":
    main()

Solution (Python):
dic, link = (dict() for i in range(2))
n = int(input())
se = set(int(x) for x in range(n))

for i in range(n):
    a, b, c = map(int, input().split())
    link[a] = list()
    for bc in [b, c]:
        link[a].append(bc)
        se.discard(bc)

rt = se.pop()
pre_odr, in_odr, pst_odr = ([] for i in range(3))


def dfs_pr(u):
    pre_odr.append(u)
    for e in link[u]:
        if e >= 0: dfs_pr(e)


def dfs_in(u):
    for i in range(2):
        if i < len(link[u]):
            if i != 0 and u not in used:
                in_odr.append(u)
                used.add(u)
            e = link[u][i]
            if e < 0: continue
            dfs_in(e)
            if e not in used:
                in_odr.append(e)
                used.add(e)


def dfs_ps(u):
    for e in link[u]:
        if e >= 0: dfs_ps(e)
    pst_odr.append(u)


print("Preorder")
dfs_pr(rt)
print("", *pre_odr)

print("Inorder")
used = set()
dfs_in(rt)
if len(in_odr) == 0: in_odr.append(0)
print("", *in_odr)

print("Postorder")
dfs_ps(rt)
print("", *pst_odr)

Solution (Python):
class BinaryTree:
    def __init__(self, parent, left, right):
        self.parent = parent
        self.left = left
        self.right = right

n = int(input().rstrip())

T = []
for _ in range(n):
    T.append(BinaryTree(-1, -1, -1))

for _ in range(n):
    input_line = list(map(int, input().rstrip().split(" ")))
    assert len(input_line) == 3, "input line should be composed of 3 items"
    u, left, right = input_line
    T[u].left = left
    T[u].right = right
    if left != -1:
        T[left].parent = u
    if right != -1:
        T[right].parent = u

def preParse(u):
    if u == -1:
        return 0
    print(" " + str(u), end="")
    preParse(T[u].left)
    preParse(T[u].right)

def inParse(u):
    if u == -1:
        return 0
    inParse(T[u].left)
    print(" " + str(u), end="")
    inParse(T[u].right)

def postParse(u):
    if u == -1:
        return 0
    postParse(T[u].left)
    postParse(T[u].right)
    print(" " + str(u), end="")


for u, t in enumerate(T):
    if t.parent == -1:
        parent = u
        break
        

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

def get_depth(T:dict,u:int):
    d = 0
    while T[u] != -1:
        u = T[u].parent
        d += 1

D = {}

def get_all_depth(T:dict,u:int,p:int):
    D[u] = p
    if T[u].left != -1:
        get_all_depth(T,T[u].left,p+1)
    if T[u].right != -1:
        get_all_depth(T,T[u].right,p+1)

H = {}

def get_all_height(T:dict,u:int):
    h1 = 0
    h2 = 0
    if T[u].right != -1:
        h1 = get_all_height(T,T[u].right)+1
    if T[u].left != -1:
        h2 = get_all_height(T,T[u].left)+1
    H[u] = max(h1,h2)
    return H[u]

def get_sibling(T:dict,u:int):
    if T[u].parent == -1:
        return -1
    if T[T[u].parent].left != u and T[T[u].parent].left != -1:
        return T[T[u].parent].left
    if T[T[u].parent].right != u and T[T[u].parent].right != -1:
        return T[T[u].parent].right
    return -1

def PRINT(T:dict,node:int,D:dict,H:dict):
    dig = (T[node].right!=-1)+(T[node].left!=-1)
    if (T[node].left==-1) and (T[node].right==-1):
        node_type = "leaf"
    else:
        node_type = "internal node"
    if T[node].parent == -1:
        node_type = "root"
    print(f"node {node}: parent = {T[node].parent}, sibling = {get_sibling(T,node)}, degree = {dig}, depth = {D[node]}, height = {H[node]}, {node_type}")

def preorder(u:int):
    if u == -1:
        return 
    print(" "+str(u),end="")
    preorder(T[u].left)
    preorder(T[u].right)

def inorder(u:int):
    if u == -1:
        return 
    inorder(T[u].left)
    print(" "+str(u),end="")
    inorder(T[u].right)

def postorder(u:int):
    if u == -1:
        return 
    postorder(T[u].left)
    postorder(T[u].right)
    print(" "+str(u),end="")

n = int(input())
T = {k: Node(-1,-1,-1) for k in range(n)}

R = -1

for _ in range(n):
    a,b,c = map(int,input().split())
    T[a].left = b
    T[a].right = c
    if b != -1:
        T[b].parent = a
    if c != -1:
        T[c].parent = a
for node in range(n):
    if T[node].parent == -1:
        R = node

print("Preorder")
preorder(R)
print("")
print("Inorder")
inorder(R)
print("")
print("Postorder")
postorder(R)
print("")

Solution (Python):
import sys

N = int(sys.stdin.readline().rstrip())  

parents = [None] * N

CHs = [[None, None] for _ in range(N)]
_Pre = []
_In = []
_Post = []




def dfs(u, r=-1):

    
    _Pre.append(u)

    if CHs[u][0] != -1:
        dfs(CHs[u][0], u)
    
    _In.append(u)

    if CHs[u][1] != -1:
        dfs(CHs[u][1], u)

    _Post.append(u)

    


def main():
    for i in range(N):
        id, lf, rg = map(int, sys.stdin.readline().rstrip().split())
        CHs[id][0] = lf
        CHs[id][1] = rg

        if lf != -1:
            parents[lf] = id
        if rg != -1:
            parents[rg] = id

    
    u = 0
    root = None
    while True:
        if parents[u] is None:
            root = u
            parents[u] = -1
            break
        u = parents[u]

    dfs(root, 0)
    print("Preorder")
    print("", *_Pre)
    print("Inorder")
    print("", *_In)
    print("Postorder")
    print("", *_Post)


main()

Solution (Python):
class Node:
    def __init__(self, no):
        self.no = no
        self.parent = -1
        self.left = self.right = -1
    def preorder(self):
        global t
        L = [self.no]
        if self.left >= 0: L += t[self.left].preorder()
        if self.right >= 0: L += t[self.right].preorder()
        return L
    def inorder(self):
        global t
        L = []
        if self.left >= 0: L += t[self.left].inorder()
        L.append(self.no)
        if self.right >= 0: L += t[self.right].inorder()
        return L
    def postorder(self):
        global t
        L = []
        if self.left >= 0: L += t[self.left].postorder()
        if self.right >= 0: L += t[self.right].postorder()
        L.append(self.no)
        return L

n = int(input())
t = [ Node(i) for i in range(n) ]
for _ in range(n):
    no, left, right = map(int, input().split())
    t[no].left = left
    t[no].right = right
    if left >= 0:
        t[left].parent = no
    if right >= 0:
        t[right].parent = no

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

print('Preorder')
print('',*t[rootno].preorder())
print('Inorder')
print('',*t[rootno].inorder())
print('Postorder')
print('',*t[rootno].postorder())

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):
import sys
sys.setrecursionlimit(10**7)

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

def preParse(T, u, pre):
    if u == -1:
        return
    pre.append(u)
    preParse(T, T[u].left, pre)
    preParse(T, T[u].right, pre)

def inParse(T, u, inl):
    if u == -1:
        return
    inParse(T, T[u].left, inl)
    inl.append(u)
    inParse(T, T[u].right, inl)

def postParse(T, u, post):
    if u == -1:
        return
    postParse(T, T[u].left, post)
    postParse(T, T[u].right, post)
    post.append(u)

n = int(input())
T = {k: Node(-1, -1, -1) for k in range(n)}  

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

for id, node in T.items():
    if node.parent == -1:
        ROOT = id

pre, inl, post = [], [], []
preParse(T, ROOT, pre)
inParse(T, ROOT, inl)
postParse(T, ROOT, post)

print('Preorder')
print('', *pre)
print('Inorder')
print('', *inl)
print('Postorder')
print('', *post)

Solution (Python):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

class Node():
    def __init__(self):
        self.left = -1
        self.right = -1
        self.parent = -1
        
T = [Node() for i in range(25)]

for (idx, left, right) in A:
    T[idx].left = left
    T[idx].right = right
    if left != -1:
        T[left].parent = idx
    if right != -1:
        T[right].parent = idx

for idx in range(n):
    if T[idx].parent == -1:
        root = idx
        break
        
preorder_list = []
def preorder(u):
    preorder_list.append(str(u))
    if T[u].left != -1:
        preorder(T[u].left)
    if T[u].right != -1:
        preorder(T[u].right)
        
inorder_list = []
def inorder(u):    
    if T[u].left != -1:
        inorder(T[u].left)
    inorder_list.append(str(u))
    if T[u].right != -1:
        inorder(T[u].right)

postorder_list = []
def postorder(u):    
    if T[u].left != -1:
        postorder(T[u].left)
    if T[u].right != -1:
        postorder(T[u].right)
    postorder_list.append(str(u))
    
preorder(root)
inorder(root)
postorder(root)

print('Preorder')
print(' '+' '.join(preorder_list))
print('Inorder')
print(' '+' '.join(inorder_list))
print('Postorder')
print(' '+' '.join(postorder_list))

Solution (Python):
class Node:
    def __init__(self, node, left, right):
        self.node = node
        self.left = left
        self.right = right
        self.parent = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = ""

    def __str__(self):
        if self.parent == -1:
            self.type = "root"
        elif self.degree == 0:
            self.type = "leaf"
        else:
            self.type = "internal node"
        return "node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
            self.node, self.parent, self.sibling, self.degree, self.depth, self.height, self.type)


preOrder = None
inOrder = None
postOrder = None


def dfs(tree, v, p, d, s):
    global preOrder, inOrder, postOrder
    preOrder.append(v)
    tree[v].parent = p
    tree[v].depth = d
    tree[v].sibling = s
    maxheight = 0
    if tree[v].left != -1:
        tree[v].degree += 1
        maxheight = max(
            maxheight, dfs(
                tree, tree[v].left, v, d + 1, tree[v].right))
    inOrder.append(v)
    if tree[v].right != -1:
        tree[v].degree += 1
        maxheight = max(
            maxheight, dfs(
                tree, tree[v].right, v, d + 1, tree[v].left))
    postOrder.append(v)
    if tree[v].left == tree[v].right:
        tree[v].height = 0
        return 0
    tree[v].height = maxheight + 1
    return tree[v].height


def resolve():
    global preOrder, inOrder, postOrder
    preOrder, inOrder, postOrder = [], [], []
    n = int(input())
    tree = [None for i in range(n)]
    V = [list(map(int, input().split())) for _ in range(n)]
    hasChild = set()
    childrens = set()
    for a, left, right in V:
        tree[a] = Node(a, left, right)
        if left != right:
            hasChild.add(a)
            childrens.add(left)
            childrens.add(right)
    root = hasChild - childrens
    if len(root) > 0:
        root = root.pop()
    else:
        root = 0
    dfs(tree, root, -1, 0, -1)
    print("Preorder")
    print("", *preOrder)
    print("Inorder")
    print("", *inOrder)
    print("Postorder")
    print("", *postOrder)


resolve()

Solution (Python):
n=int(input())

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

ns=[Node() for i in range(n)]

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="")

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):
ID,LEFT,RIGHT = 0,1,2
n = int(input())

preorder_list = []
def preorder(node):
  preorder_list.append(node[0][ID])
  if node[0][LEFT] != -1:
    preorder(nodes[node[0][LEFT]])
  if node[0][RIGHT] != -1:
    preorder(nodes[node[0][RIGHT]])

inorder_list = []
def inorder(node):
  if node[0][LEFT] != -1:
    inorder(nodes[node[0][LEFT]])
  inorder_list.append(node[0][ID])
  if node[0][RIGHT] != -1:
    inorder(nodes[node[0][RIGHT]])

postorder_list = []
def postorder(node):
  if node[0][LEFT] != -1:
    postorder(nodes[node[0][LEFT]])
  if node[0][RIGHT] != -1:
    postorder(nodes[node[0][RIGHT]])
  postorder_list.append(node[0][ID])

nodes = [[] for _ in range(n)]
for i in range(n):
  id, left, right = list(map(int, input().split()))
  nodes[id].append({ID:id, LEFT:left, RIGHT:right})

id_list = [0 for _ in range(n)]
for node in nodes:
  if node[0][LEFT] != -1:
    id_list[node[0][LEFT]] += 1
  if node[0][RIGHT] != -1:
    id_list[node[0][RIGHT]] += 1

root_id = -1
for i,v in enumerate(id_list):
  if v == 0:
    root_id = i
    break


preorder(nodes[root_id])
print ('Preorder')
print (' '+' '.join(map(str, preorder_list)))
inorder(nodes[root_id])
print ('Inorder')
print (' '+' '.join(map(str, inorder_list)))
postorder(nodes[root_id])
print ('Postorder')
print (' '+' '.join(map(str, postorder_list)))

Solution (Python):
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    children = [[] for _ in range(n)]
    parent = [-1]*n
    for _ in range(n):
        ilr = LI()
        id = ilr[0]
        left = ilr[1]
        right = ilr[2]
        children[id] = (left, right)
        if left>=0: parent[left] = id
        if right>=0: parent[right] = id

    preorder = []
    inorder = []
    postorder = []

    def dfs(v):
        preorder.append(v)
        c0, c1 = children[v]
        if c0!=-1:
            dfs(c0)
        inorder.append(v)
        if c1!=-1:
            dfs(c1)
        postorder.append(v)
    
    root = parent.index(-1)
    dfs(root)

    print('Preorder')
    print('', *preorder)
    print('Inorder')
    print('', *inorder)
    print('Postorder')
    print('', *postorder)

if __name__ == '__main__':
    resolve()