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.



Sample input:
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:
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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

Submission status: Accepted

Solution code:
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.nodes[i].num] + self.print_inorder(self.nodes[i].left)
            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.nodes[i].num] + self.print_postorder(self.nodes[i].right)
            return self.print_postorder(self.nodes[i].right) + [self.nodes[i].num] 
        elif self.nodes[i].right == -1:
#            return [self.nodes[i].num] + self.print_postorder(self.nodes[i].left)
            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())

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

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()

Submission status: Accepted

Solution code:
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)]

    ## create binary tree
    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]

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

    ## preorder tree walk
    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 tree walk

    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 walk

    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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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="")

# find parent
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()

Submission status: Accepted

Solution code:
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("")

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().rstrip())  # 節点数

parents = [None] * N

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

# ## DFS ## #


def dfs(u, r=-1):

    # u を訪れたときの処理
    _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)

    # 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()

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2 ** 20)  # 再帰回数上限の向上 かなり多くしないとREになる


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


n = int(input())
T = {key: Node(None, None, None) for key in range(n)}  # 初期化
for _ in range(n):
    tmp = list(map(int, input().split()))
    # 左から処理
    if tmp[1] != -1:
        T[tmp[0]].left = tmp[1]  # 子の代入
        T[tmp[1]].parent = tmp[0]  # 親の代入
    if tmp[2] != -1:
        T[tmp[0]].right = tmp[2]  # 子の代入
        T[tmp[2]].parent = tmp[0]  # 親の代入


def preorder(t: dict, p: int, pre_ls: list):
    pre_ls.append(p)
    if t[p].left is not None:
        preorder(t, t[p].left, pre_ls)
    if t[p].right is not None:
        preorder(t, t[p].right, pre_ls)


def inorder(t: dict, p: int, in_ls: list):
    if t[p].left is not None:
        inorder(t, t[p].left, in_ls)
    in_ls.append(p)
    if t[p].right is not None:
        inorder(t, t[p].right, in_ls)


def postorder(t: dict, p: int, post_ls: list):
    if t[p].left is not None:
        postorder(t, t[p].left, post_ls)
    if t[p].right is not None:
        postorder(t, t[p].right, post_ls)
    post_ls.append(p)


for id, node in T.items():
    if node.parent is None:
        ROOT = id

a, b, c = [], [], []
preorder(T, ROOT, a)
inorder(T, ROOT, b)
postorder(T, ROOT, c)

print('Preorder')
print('', *a)
print('Inorder')
print('', *b)
print('Postorder')
print('', *c)

Submission status: Accepted

Solution code:
def dfs(nodes, v):

    preorder.append(v)
    if nodes[v][0] != -1:
        dfs(nodes, nodes[v][0])

    inorder.append(v)

    if nodes[v][1] != -1:
        dfs(nodes, nodes[v][1])

    postorder.append(v)


def main():
    global preorder
    global inorder
    global postorder

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

    n = int(input())
    in_num = [0] * n
    nodes = [[] for _ in range(n)]
    for i in range(n):
        tree = list(map(int, input().split()))
        node = tree[0]
        left = tree[1]
        right = tree[2]

        nodes[node].append(left)
        nodes[node].append(right)

        if left != -1:
            in_num[left] += 1
        if right != -1:
            in_num[right] += 1

    for i in range(len(in_num)):
        if in_num[i] == 0:
            root_node = i
            break

    dfs(nodes, root_node)
    print("Preorder")
    print("", *preorder)
    print("Inorder")
    print("", *inorder)
    print("Postorder")
    print("", *postorder)


if __name__ == '__main__':
    main()