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:
class Node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

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

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

def preParse(u):
    if u == -1: return
    preorder.append(u)
    preParse(T[u].l)
    preParse(T[u].r)

def inParse(u):
    if u == -1: return
    inParse(T[u].l)
    inorder.append(u)
    inParse(T[u].r)

def postParse(u):
    if u == -1: return
    postParse(T[u].l)
    postParse(T[u].r)
    postorder.append(u)

r = 0
while T[r].p != -1: r += 1
preParse(r)
inParse(r)
postParse(r)

print("Preorder",end="\n ")
print(*preorder)
print("Inorder",end="\n ")
print(*inorder)
print("Postorder",end="\n ")
print(*postorder)

Submission status: Accepted

Solution code:
# Tree walk 木の巡回


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


def preordertreewalk(u):
    print(" ", u, end="", sep="")
    if T[u].left != -1:
        preordertreewalk(T[u].left)
    if T[u].right != -1:
        preordertreewalk(T[u].right)


def inordertreewalk(u):
    if T[u].left != -1:
        inordertreewalk(T[u].left)
    print(" ", u, end="", sep="")
    if T[u].right != -1:
        inordertreewalk(T[u].right)


def postordertreewalk(u):
    if T[u].left != -1:
        postordertreewalk(T[u].left)
    if T[u].right != -1:
        postordertreewalk(T[u].right)
    print(" ", u, end="", sep="")


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

rootid = -1
for id in range(n):
    if T[id].parent == -1:
        rootid = id

print("Preorder")
preordertreewalk(rootid)

print("\nInorder")
inordertreewalk(rootid)

print("\nPostorder")
postordertreewalk(rootid)
print()

Submission status: Accepted

Solution code:
global nodes

class Node:
    def _init__(self):
        self.left = -1
        self.right = -1
    def set(self,arg_node_left,arg_node_right):
        self.left =arg_node_left
        self.right =arg_node_right
    
def Preorder(node_id):
    print(" %d"%(node_id),end="")
    if nodes[node_id].left != -1:
        Preorder(nodes[node_id].left)
    if nodes[node_id].right != -1:
        Preorder(nodes[node_id].right)

def Inorder(node_id):
    if nodes[node_id].left != -1:
        Inorder(nodes[node_id].left)
    print(" %d"%(node_id),end="")
    if nodes[node_id].right != -1:
        Inorder(nodes[node_id].right)

def Postorder(node_id):
    if nodes[node_id].left != -1:
        Postorder(nodes[node_id].left)
    if nodes[node_id].right != -1:
        Postorder(nodes[node_id].right)
    print(" %d"%(node_id),end="")

V = int(input())
nodes = [Node() for _ in range(V)]
in_num = [0]*V
for loop in range(V):
    node_id,left,right = map(int,input().split())
    nodes[node_id].set(left,right)
    if left != -1:
        in_num[left] += 1
    if right != -1:
        in_num[right] += 1

root = -1 #rootを探す
for i in range(V): 
    if in_num[i] == 0:
        root = i
        break

print("Preorder")
Preorder(root)
print()

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

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

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [[int(item) for item in input().split()] for _ in range(N)]
    A_list.sort(key=lambda x:x[0])

    def is_root(node):
        root_check_que = collections.deque([node])
        foot_print = [False for _ in range(N)]

        while root_check_que:
            temp_node = root_check_que.popleft()
            foot_print[temp_node] = True
            children = A_list[temp_node][1:3]

            for child in children:
                if child >= 0 and foot_print[child] == False:
                    root_check_que.append(child)

        return all(foot_print)


    def preorder(node):
        if node == -1:
            return

        print('',node, end='')
        left = A_list[node][1]
        right = A_list[node][2]
        preorder(left)
        preorder(right)

    for i in range(N):
        if is_root(i):
            root = i
            break

    def inorder(node):
        if node == -1:
            return

        left = A_list[node][1]
        right = A_list[node][2]
        inorder(left)
        print('',node, end='')
        inorder(right)
    
    def postorder(node):
        if node == -1:
            return

        left = A_list[node][1]
        right = A_list[node][2]
        postorder(left)
        postorder(right)
        print('',node, end='')

    for i in range(N):
        if is_root(i):
            root = i
            break
    
    print('Preorder')
    preorder(root)
    print('')


    print('Inorder')
    inorder(root)
    print('')

    print('Postorder')
    postorder(root)
    print('')


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# Tree Walk


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


class BinaryTree():
    def __init__(self, n):
        self.T = [Node(i) for i in range(n)]
        self.preorder_idx = []
        self.inorder_idx = []
        self.postorder_idx = []

    def set_children(self, idx, l, r):
        node = self.T[idx]
        node.left = l
        node.right = r
        if l != -1:
            self.T[l].parent = idx
        if r != -1:
            self.T[r].parent = idx

    def get_root(self):
        for idx, node in enumerate(self.T):
            if node.parent == -1:
                return idx

    def preorder(self, idx):
        if idx == -1:
            return
        node = self.T[idx]
        self.preorder_idx.append(idx)
        self.preorder(node.left)
        self.preorder(node.right)

    def inorder(self, idx):
        if idx == -1:
            return
        node = self.T[idx]
        self.inorder(node.left)
        self.inorder_idx.append(idx)
        self.inorder(node.right)

    def postorder(self, idx):
        if idx == -1:
            return
        node = self.T[idx]
        self.postorder(node.left)
        self.postorder(node.right)
        self.postorder_idx.append(idx)


N = int(input())
tree = BinaryTree(N)

for _ in range(N):
    idx, l, r = map(int, input().split())
    tree.set_children(idx, l, r)

root = tree.get_root()
tree.preorder(root)
tree.inorder(root)
tree.postorder(root)

print('Preorder')
print('', *(tree.preorder_idx))
print('Inorder')
print('', *(tree.inorder_idx))
print('Postorder')
print('', *(tree.postorder_idx))

Submission status: Accepted

Solution code:
class node(object):
    def __init__(self):
        self.value = None
        self.left = None
        self.right = None
        self.parent = None

def preorder(nodes,root):
    stacked = [nodes[root]]
    visited = []
    while(len(stacked)>0):
        node = stacked.pop()
        value = node.value
        left = node.left
        right = node.right
        visited.append(value)
        
        if (right not in visited) and (right != None):
            stacked.append(nodes[right])
        if (left not in visited) and (left != None):
            stacked.append(nodes[left])
    out = ""
    for i in visited:
        out += " "+str(i)
    return out

def inorder_search(cur,nodes,out_list):
    value,left,right = nodes[cur].value,nodes[cur].left,nodes[cur].right
    if left != None:
        inorder_search(left,nodes,out_list)
    out_list.append(value)
    if right != None:
        inorder_search(right,nodes,out_list)

def inorder(nodes,root):
    out_list = []
    cur = root
    inorder_search(cur,nodes,out_list)
    out = ""
    for i in out_list:
        out += " "+str(i)
    return out

def postorder_search(cur,nodes,out_list):
    value,left,right = nodes[cur].value,nodes[cur].left,nodes[cur].right

    if left != None:
        postorder_search(left,nodes,out_list)
    if right != None:
        postorder_search(right,nodes,out_list)
    out_list.append(value)

def postorder(nodes,root):
    out_list = []
    cur = root

    postorder_search(cur,nodes,out_list)
    out = ""
    for i in out_list:
        out += " "+str(i)
    return out

if __name__ == "__main__":
    n = int(input())
    nodes = [node() for _ in range(n)]
    for i in range(n):
        value,left,right = map(int,input().split())
        nodes[value].value = value
        if right != -1:
            nodes[value].right = right
            nodes[right].parent = value
        if left != -1:
            nodes[value].left = left
            nodes[left].parent = value
    root = 0
    for i in range(n):
        if nodes[i].parent is None:
            root = i

    print("Preorder")
    print(preorder(nodes,root))
    print("Inorder")
    print(inorder(nodes,root))
    print("Postorder")
    print(postorder(nodes,root))

Submission status: Accepted

Solution code:
import sys
n = int(input())
class Node:
  def __init__(self):
    self.p = -1 # parent
    self.l = -1 # left most child
    self.r = -1 # right sibling

T = [Node() for _ in range(n)]
sys.setrecursionlimit(1500)

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

for i in range(n):
  #print(i,T[i].p,T[i].l,T[i].r)
  if T[i].p == -1 : r = i

ret = []
def preorder(v):
  if v == -1: return
  ret.append(v)
  preorder(T[v].l)
  preorder(T[v].r)

def inorder(v):
  if v == -1: return
  inorder(T[v].l)
  ret.append(v)
  inorder(T[v].r)

def postorder(v):
  if v == -1: return
  postorder(T[v].l)
  postorder(T[v].r)
  ret.append(v)

ret = []
preorder(r)
print("Preorder")
print(""," ".join(map(str,ret)))
ret = []
inorder(r)
print("Inorder")
print(""," ".join(map(str,ret)))
ret = []
postorder(r)
print("Postorder")
print(""," ".join(map(str,ret)))

Submission status: Accepted

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

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

def Inorder_Tree_Walk(T, u):   
    if u == -1:
        return

    Inorder_Tree_Walk(T, T[u].left)
    print(" " + str(u), end="")
    Inorder_Tree_Walk(T, T[u].right)

def Postorder_Tree_Walk(T, u):    
    if u == -1:
        return

    Postorder_Tree_Walk(T, T[u].left)
    Postorder_Tree_Walk(T, T[u].right)
    print(" " + str(u), end="")

def Main():

    n = int(input())
    T = [Node(-1, -1, -1) for i in range(n)]

    for i in range(n):
        node_id, left, right = map(int, input().split())

        T[node_id].left = left
        T[node_id].right = right

        if left != -1:
            T[left].parent = node_id
        if right != -1:
            T[right].parent = node_id

    r = 0
    for i in range(len(T)):
        if T[i].parent == -1:
            r = i
            
    print("Preorder")
    Preorder_Tree_Walk(T, r)
    print()
    print("Inorder")
    Inorder_Tree_Walk(T, r)
    print()
    print("Postorder")
    Postorder_Tree_Walk(T, r)
    print()

Main()

Submission status: Accepted

Solution code:
from collections import defaultdict

class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    self.parent = -1


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

def preorder_dfs(root):
  if root is None: return

  preorder.append(root.val)

  preorder_dfs(root.left)
  preorder_dfs(root.right)

def inorder_dfs(root):
  if root is None: return

  inorder_dfs(root.left)

  inorder.append(root.val)

  inorder_dfs(root.right)


def postorder_dfs(root):
  if root is None: return 
  
  postorder_dfs(root.left)
  postorder_dfs(root.right)

  postorder.append(root.val) 


num = int(input())
nodes = defaultdict(int)

for i in range(num):
  val, left, right = list(map(int, input().split()))

  if nodes[val] == 0:
    nodes[val] = TreeNode(val)
  n = nodes[val]
  
  if left != -1:
    # initalize treenode
    if nodes[left] == 0:
      nodes[left] = TreeNode(left)

    # appending to n.left
    n.left = nodes[left]
    n.left.parent = n.val

  if right != -1:
    if nodes[right] == 0:
      nodes[right] = TreeNode(right)

    n.right = nodes[right]
    n.right.parent = n.val

root = [node for node in nodes.values() if node.parent == -1][0]

preorder_dfs(root)
inorder_dfs(root)
postorder_dfs(root)

print("Preorder")
print(" " + " ".join([ str(i) for i in preorder]))
print("Inorder")
print(" " + " ".join([ str(i) for i in inorder]))
print("Postorder")
print(" " + " ".join([ str(i) for i in postorder]))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, num=None, parent=None, left=None, right=None, type=None):
        self.num = num
        self.parent = parent
        self.left = left
        self.right = right
        self.type = type

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

def getType(node):
    if node.parent is None:
        return 'root'
    elif node.left is None and node.right is None:
        return 'leaf'
    else:
        return 'internal node'

def addNodeNumToResult (node, result):
    """
    Add node number to a list (converted to string)
    :param node: a node
    :param result: a list that stores result
    :return: Nothing
    """
    result.append(str(node.num))

def preParse(node, result):
    if node is None:
        return
    addNodeNumToResult(node, result)
    preParse(node.left, result)
    preParse(node.right, result)

def inParse(node, result):
    if node is None:
        return
    inParse(node.left, result)
    addNodeNumToResult(node, result)
    inParse(node.right, result)

def postParse(node, result):
    if node is None:
        return
    postParse(node.left, result)
    postParse(node.right, result)
    addNodeNumToResult(node, result)

# import sys
# sys.stdin = open('input.txt', 'r')

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

# Initiate all nodes
for i in range(n):
    node = Node(i)
    nodes.append(node)

# Set parent, left and right from input
for i in range(n):
    num, leftNum, rightNum = map(int, input().split())
    node = nodes[num]
    if leftNum != -1:
        node.left = nodes[leftNum]
        node.left.parent = node
    if rightNum != -1:
        node.right = nodes[rightNum]
        node.right.parent = node

# Get root node
for node in nodes:
    node.type = getType(node)
    if node.type == 'root':
        root = node

result = []
preParse(root, result)
print('Preorder')
print('', end=' ')
print(' '.join(result))

result = []
inParse(root, result)
print('Inorder')
print('', end=' ')
print(' '.join(result))

result = []
postParse(root, result)
print('Postorder')
print('', end=' ')
print(' '.join(result))

Submission status: Accepted

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

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


def preorder(nodes, cur_id, result):
    node = nodes[cur_id]
    result.append(node.id)
    if node.left >= 0:
        preorder(nodes, node.left, result)
    if node.right >= 0:
        preorder(nodes, node.right, result)
    
    return


def inorder(nodes, cur_id, result):
    node = nodes[cur_id]
    if node.left >= 0:
        inorder(nodes, node.left, result)
    result.append(node.id)
    if node.right >= 0:
        inorder(nodes, node.right, result)
    
    
def postorder(nodes, cur_id, result):
    node = nodes[cur_id]
    if node.left >= 0:
        postorder(nodes, node.left, result)
    if node.right >= 0:
        postorder(nodes, node.right, result)
    result.append(node.id)


N = int(input())
nodes = [Node(i) for i in range(N)]
for i in range(N):
    id, left, right = [int(i) for i in input().split()]
    nodes[id].left, nodes[id].right = left, right
    if left >= 0:
        nodes[left].parent = id
    if right >= 0:
        nodes[right].parent = right

root = 0
for i in range(N):
    if nodes[i].parent == -1:
        root = i
        break

print('Preorder')
result = []
preorder(nodes, root, result)
print('', *result)

print('Inorder')
result = []
inorder(nodes, root, result)
print('', *result)

print('Postorder')
result = []    
postorder(nodes, root, result)
print('', *result)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001


global nodes

class Node:
    def __init__(self):
        self.left = -1
        self.right = -1
    def set(self,arg_node_left,arg_node_right):
        self.left = arg_node_left
        self.right = arg_node_right


def Preorder(node_id):
    print(" %d"%(node_id),end = "")

    if nodes[node_id].left != -1:
        Preorder(nodes[node_id].left)

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


def Inorder(node_id):

    if nodes[node_id].left != -1:
        Inorder(nodes[node_id].left)

    print(" %d"%(node_id),end = "")

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


def Postorder(node_id):

    if nodes[node_id].left != -1:
        Postorder(nodes[node_id].left)

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

    print(" %d"%(node_id),end = "")




V = int(input())
nodes = [Node() for _ in range(V)]
in_num = [0]*V


for loop in range(V):
    node_id,left,right = map(int,input().split())
    nodes[node_id].set(left,right)
    if left != -1:
        in_num[left] += 1
    if right != -1:
        in_num[right] += 1

root = -1

for i in range(V):
    if in_num[i] == 0:
        root = i
        break

print("Preorder")
Preorder(root)
print()

print("Inorder")
Inorder(root)
print()

print("Postorder")
Postorder(root)
print()

Submission status: Accepted

Solution code:
from collections.abc import Iterable

n = int(input())
nodes = {}
for _ in range(n):
    key, left, right = map(int, input().split())
    nodes[key] = (left, right)
keys = set(nodes.keys())
for left, right in nodes.values():
    keys -= {left, right}
root = keys.pop()


def flatten(arr):
    for a in arr:
        if isinstance(a, Iterable) and not isinstance(a, (str, bytes)):
            yield from flatten(a)
        else:
            yield a


def pre_tw(key):
    left, right = nodes[key]
    if left == -1 and right == -1:
        return [key]
    elif left == -1:
        return [key, pre_tw(right)]
    elif right == -1:
        return [key, pre_tw(left)]
    else:
        return [key, pre_tw(left), pre_tw(right)]


def in_tw(key):
    left, right = nodes[key]
    if left == -1 and right == -1:
        return [key]
    elif left == -1:
        return [key, in_tw(right)]
    elif right == -1:
        return [in_tw(left), key]
    else:
        return [in_tw(left), key, in_tw(right)]


def post_tw(key):
    left, right = nodes[key]
    if left == -1 and right == -1:
        return [key]
    elif left == -1:
        return [post_tw(right), key]
    elif right == -1:
        return [post_tw(left), key]
    else:
        return [post_tw(left), post_tw(right), key]


print("Preorder")
for a in flatten(pre_tw(root)):
    print(" {}".format(a), end="")
print()

print("Inorder")
for a in flatten(in_tw(root)):
    print(" {}".format(a), end="")
print()

print("Postorder")
for a in flatten(post_tw(root)):
    print(" {}".format(a), end="")
print()

Submission status: Accepted

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

p = [-1]*n
r = [-1]*n
l = [-1]*n

for i in range(n):
    ind = a[i][0]
    r[ind] = a[i][2]
    l[ind] = a[i][1]
    if r[ind]>=0:
        p[r[ind]] = ind
    if l[ind]>=0:
        p[l[ind]] = ind

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

def preorder(ind):
    print(' %i'%ind, end='')
    if l[ind]!=-1:
        preorder(l[ind])
    if r[ind]!=-1:
        preorder(r[ind])
        
def inorder(ind):
    if l[ind]!=-1:
        inorder(l[ind])
    print(' %i'%ind, end='')
    if r[ind]!=-1:
        inorder(r[ind])
        
def postorder(ind):
    if l[ind]!=-1:
        postorder(l[ind])
    if r[ind]!=-1:
        postorder(r[ind])
    print(' %i'%ind, end='')
    
print('Preorder')
preorder(root)
print()
print('Inorder')
inorder(root)
print()
print('Postorder')
postorder(root)
print()

Submission status: Accepted

Solution code:
N = int(input())
T = [list(map(int,input().split())) for _ in range(N)]

T.sort(key = lambda x:x[0])

class Node:
    def __init__(self,data,l_child,r_child):
        self.data = data
        self.l_child = l_child
        self.r_child = r_child

T = [Node(T[i][0],T[i][1],T[i][2]) for i in range(N)]

P = [-1 for _ in range(N)]
for i in range(N):
    if T[i].l_child != -1:
        P[T[i].l_child] = T[i].data
    if T[i].r_child != -1:
        P[T[i].r_child] =T[i].data
for i in range(N):
    if P[i] == -1:
        root = i

def Pre_patrol(node,List):
    if node.data != -1:
        List.append(node.data)
        if node.l_child != -1:
            Pre_patrol(T[node.l_child],List)
        if node.r_child != -1:
            Pre_patrol(T[node.r_child],List)
    return List

def In_patrol(node,List):
    if node.data != -1:
        if node.l_child != -1:
            In_patrol(T[node.l_child],List)
        List.append(node.data)
        if node.r_child != -1:
            In_patrol(T[node.r_child],List)
    return List

def Pos_patrol(node,List):
    if node.data != -1:
        if node.l_child != -1:
            Pos_patrol(T[node.l_child],List)
        if node.r_child != -1:
            Pos_patrol(T[node.r_child],List)
        List.append(node.data)
    return List

print("Preorder")
for i in range(N):
    print(" "+str(Pre_patrol(T[root],[])[i]),end="")
print()
print("Inorder")
for i in range(N):
    print(" "+str(In_patrol(T[root],[])[i]),end="")
print()
print("Postorder")
for i in range(N):
    print(" "+str(Pos_patrol(T[root],[])[i]),end="")
print()

Submission status: Accepted

Solution code:
N = int(input())
tree = [{'parent': -1, 'left': -1, 'right': -1, 'sibling': -1} for _ in range(N)]
parent = set(n for n in range(N))

for _ in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]['left'] = inp[1]
    tree[inp[0]]['right'] = inp[2]

    if inp[1] != -1:
        tree[inp[1]]['parent'] = inp[0]
        tree[inp[1]]['sibling'] = inp[2]
    if inp[2] != -1:
        tree[inp[2]]['parent'] = inp[0]
        tree[inp[2]]['sibling'] = inp[1]
    parent = parent.difference(inp[1:])

root = parent.pop()

def preParse(u):
    if u == -1:
        return 
    print(f' {u}', end = '')
    preParse(tree[u]['left'])
    preParse(tree[u]['right'])

def inParse(u):
    if u == -1:
        return 
    inParse(tree[u]['left'])
    print(f' {u}', end = '')
    inParse(tree[u]['right'])

def postParse(u):
    if u == -1:
        return 
    postParse(tree[u]['left'])
    postParse(tree[u]['right'])
    print(f' {u}', end = '')

print('Preorder')
preParse(root)
print()

print('Inorder')
inParse(root)
print()

print('Postorder')
postParse(root)
print()

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None
        self.marked = 0
    def setLeft(self, left):
        left.parent = self
        self.left = left
    def setRight(self, right):
        right.parent = self
        self.right = right
    def __str__(self):
        return str(self.id)


def preorder(arr, root, res):
    if root == None:
        return
    res.append(root)
    preorder(arr, root.left, res)
    preorder(arr, root.right, res)

def inorder(arr, root, res):
    if root == None:
        return
    inorder(arr, root.left, res)
    res.append(root)
    inorder(arr, root.right, res)

def postorder(arr, root, res):
    if root == None:
        return
    postorder(arr, root.left, res)
    postorder(arr, root.right, res)
    res.append(root)


def main():
    n = int(input())
    array = [Node(i) for i in range(n)]
    for node in array:
        i, l, r = list(map(int, input().split()))
        array[i].setLeft(array[l]) if l != -1 else None
        array[i].setRight(array[r]) if r != -1 else None
    
    root = None
    for node in array:
        if node.parent == None:
            root = node
            break

    res = []
    preorder(array, root, res)
    print("Preorder\n ", end="")
    print(*res) 
    res = [] 
    inorder(array, root, res)
    print("Inorder\n ", end="")
    print(*res)
    res = []
    postorder(array, root, res)
    print("Postorder\n ", end="")
    print(*res)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    from collections import defaultdict

    NIL = -1

    n = int(input())

    # pythonは構造体を用意するのに手間取るので、辞書型を使う
    T = defaultdict(lambda: {'l':NIL, 'r':NIL, 'p':NIL})

    for _ in range(n):
        u, l, r = map(int, input().split())
        T[u]['l'] = l
        T[u]['r'] = r
        if l != NIL:
            T[l]['p'] = u
        if r != NIL:
            T[r]['p'] = u

    for u, info in T.items():
        if info['p'] == NIL:
            root = u
            break

    # 先行順巡回
    def pre_parse(u):
        if u == NIL:
            return
        print(' ' + str(u), end='')
        pre_parse(T[u]['l'])
        pre_parse(T[u]['r'])

    # 中間順巡回
    def in_parse(u):
        if u == NIL:
            return
        in_parse(T[u]['l'])
        print(' ' + str(u), end='')
        in_parse(T[u]['r'])

    # 後行順巡回
    def post_parse(u):
        if u == NIL:
            return
        post_parse(T[u]['l'])
        post_parse(T[u]['r'])
        print(' ' + str(u), end='')

    print('Preorder')
    pre_parse(root)
    print('')

    print('Inorder')
    in_parse(root)
    print('')

    print('Postorder')
    post_parse(root)
    print('')

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    parent, children = {}, {}
    preorder, inorder, postorder = [], [], []
    n = int(input())
    for _ in range(n):
        i, left, right = input().split()
        children[i] = dict(right=right, left=left)
        for child in children[i].values():
            if child != "-1":
                parent[child] = i
    
    root = (set(children) - set(parent)).pop()
    parent[root] = "-1"
    
    def set_preorder(i):
        if i == "-1":
            return
        preorder.append(i)
        set_preorder(children[i]["left"])
        set_preorder(children[i]["right"])
    
    def set_inorder(i):
        if i == "-1":
            return
        set_inorder(children[i]["left"])
        inorder.append(i)
        set_inorder(children[i]["right"])

    def set_postorder(i):
        if i == "-1":
            return
        set_postorder(children[i]["left"])
        set_postorder(children[i]["right"])
        postorder.append(i)
                
    set_preorder(root)
    set_inorder(root)
    set_postorder(root)

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

Submission status: Accepted

Solution code:
N = int(input())
nodes = [[-1,-1,-1] for i in range(N)]

for k in range(N):
    i,l,r = map(int,input().split())
    nodes[i][1] = l
    nodes[i][2] = r
    if l != -1:
        nodes[l][0] = i
    if r != -1:
        nodes[r][0] = i

#print(nodes)

def preParse(u):
    if u == -1:
        return
    print(' {}'.format(u), end='')
    preParse(nodes[u][1])
    preParse(nodes[u][2])

def inParse(u):
    if u == -1:
        return
    inParse(nodes[u][1])
    print(' {}'.format(u), end='')
    inParse(nodes[u][2])

def postParse(u):
    if u == -1:
        return
    postParse(nodes[u][1])
    postParse(nodes[u][2])
    print(' {}'.format(u), end='')

root = 0
while nodes[root][0] != -1:
    root = nodes[root][0]

print('Preorder')
preParse(root)
print()

print('Inorder')
inParse(root)
print()

print('Postorder')
postParse(root)
print()