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 BinaryTree:
    class Node:
        def __init__(self, nid, left, right):
            self.id = nid
            self.left = left
            self.right = right

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

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

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

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

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

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

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

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

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

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

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

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


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

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

    tree = BinaryTree.create(nodeids)

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


if __name__ == '__main__':
    run()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
from enum import Enum, auto
from collections import deque

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

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

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

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

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

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

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

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

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

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

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

print('Preorder') # 根節点、左部分木、右部分木の順
preordered = []
preorder_bfs(root)
print_elements(preordered)

print('Inorder') # 左部分木、根節点、右部分木の順
inordered = []
inorder_dfs_init(root)
print_elements(inordered)

print('Postorder') # 左部分木、右部分木、根節点の順
postordered = []
postorder_dfs_init(root)
print_elements(postordered)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 19 19:34:44 2018
ALDS1_7_B
@author: maezawa
"""

n = int(input())

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

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

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

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

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

def get_height(i):
    return height[i]

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

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

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

Submission status: Accepted

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


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


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

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


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

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


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

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


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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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


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

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

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

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

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

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

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

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

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


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

Submission status: Accepted

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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


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


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


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


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

root = ps.index(-1)

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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


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

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

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

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

Submission status: Accepted

Solution code:
Parent = 0
Lchild = 1
Rchild = 2

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


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


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


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


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


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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
def pre(k):
    global nodes

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

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

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

def ino(k):
    global nodes

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

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

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


def pos(k):
    global nodes

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

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


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



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

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


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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

#make_tree
for _ in range(N):
    #id, left, right
    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
        
#search_root
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)

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

Submission status: Accepted

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