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: Wrong Answer

Solution code:
from sys import stdin

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

def print_nodes(nodes, n):
    A = []
    B = []
    C = []
    def walk_tree(nodes, u):
        if u == -1:
            return
        r = nodes[u].right
        l = nodes[u].left
        nonlocal A
        A.append(u)
        walk_tree(nodes, l)
        B.append(u)
        walk_tree(nodes, r)
        C.append(u)

    for i in range(n):
        if nodes[i].parent == None:
            walk_tree(nodes, i)
            print("Preorder")
            print(*A, sep=" ")
            print("Ineorder")
            print(*B, sep=" ")
            print("Postorder")
            print(*C, sep=" ")

def read_binary_tree(nodes, n):
    for _ in range(n):
        i = [int(i) for i in stdin.readline().strip().split()]
        nodes[i[0]].left = i[1]
        nodes[i[0]].right = i[2]
        if i[1] != -1:
            nodes[i[1]].parent = i[0]
        if i[2] != -1:
            nodes[i[2]].parent = i[0]

n = int(input())
nodes = [Node() for _ in range(n)]
read_binary_tree(nodes, n)
print_nodes(nodes, n)

Submission status: Wrong Answer

Solution code:
from sys import stdin

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

def print_nodes(nodes, n):
    A = []
    B = []
    C = []
    def walk_tree(nodes, u):
        if u == -1:
            return
        r = nodes[u].right
        l = nodes[u].left
        nonlocal A
        A.append(u)
        walk_tree(nodes, l)
        B.append(u)
        walk_tree(nodes, r)
        C.append(u)

    for i in range(n):
        if nodes[i].parent == None:
            walk_tree(nodes, i)
            print("Preorder", end="\n ")
            print(*A, sep=" ")
            print("Ineorder", end="\n ")
            print(*B, sep=" ")
            print("Postorder", end="\n ")
            print(*C, sep=" ")

def read_binary_tree(nodes, n):
    for _ in range(n):
        i = [int(i) for i in stdin.readline().strip().split()]
        nodes[i[0]].left = i[1]
        nodes[i[0]].right = i[2]
        if i[1] != -1:
            nodes[i[1]].parent = i[0]
        if i[2] != -1:
            nodes[i[2]].parent = i[0]

n = int(input())
nodes = [Node() for _ in range(n)]
read_binary_tree(nodes, n)
print_nodes(nodes, n)

Submission status: Wrong Answer

Solution code:
class Trees():
    def __init__(self):
        self.nodes = {}
    def add_nodes(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)
    def add_child(self, id, child_id1, child_id2):
        for child_id in [child_id1, child_id2]:
            if child_id != -1:
                self.add_nodes(child_id)
                self.nodes[id].add_child_id(self.nodes[child_id])
        if child_id1 != -1:
            self.nodes[child_id1].sibling = child_id2
        if child_id2 != -1:            
            self.nodes[child_id2].sibling = child_id1
        self.nodes[id].left = child_id1
        self.nodes[id].right = child_id2
    def setheight(self, id):
        h1, h2 = 0, 0
        if self.nodes[id].right != -1:
            h1 = self.setheight(self.nodes[id].right) + 1
        if self.nodes[id].left != -1:
            h2 = self.setheight(self.nodes[id].left) + 1
        self.nodes[id].height = max(h1, h2)
        return max(h1, h2)
    def preorder(self,u):
        if u == -1:
            return
        print(f' {u}', end='')
        self.preorder(self.nodes[u].left)
        self.preorder(self.nodes[u].right)

    def inorder(self,u):
        if u == -1:
            return
        self.inorder(self.nodes[u].left)
        print(f' {u}', end='')
        self.inorder(self.nodes[u].right)
    def postorder(self,u):
        if u == -1:
            return
        self.postorder(self.nodes[u].left)
        self.postorder(self.nodes[u].right)
        print(f' {u}', end='')
    
        

         
class Node():
    def __init__(self, id):
        self.node = id
        self.parent = None
        self.depth = 0
        self.nodetype = 'root'
        self.children = []
        self.sibling = -1
        self.degree = 0
        self.height = 0
        self.left = -1
        self.right = -1
     
    def add_child_id(self, child):
        child.parent = self
        self.children.append(child)
        child.update_depth()
        self.update_nodetype()
        child.update_nodetype()
        self.degree += 1
        
     
    def update_depth(self):
        depth = self.depth
        if self.parent:
            self.depth = self.parent.depth + 1
        if depth != self.depth:
            for child in self.children:
                child.update_depth()
 
     
    def update_nodetype(self):
        if self.depth == 0:
            self.nodetype = 'root'
        elif len(self.children) > 0:
            self.nodetype = 'internal node'
        else:
            self.nodetype = 'leaf'
            

     
    def __str__(self):
        parent = self.parent.node if self.parent else -1
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.node, parent, self.sibling, self.degree, self.depth, self.height, self.nodetype)
     
 
tree = Trees()
 
n = int(input())
 
for i in range(n):
    a = list(map(int,input().split()))
    tree.add_nodes(a[0])
    tree.add_child(id=a[0], child_id1=a[1], child_id2=a[2])

for id in range(n):
    tree.setheight(id)
        

print('Preorder')
tree.preorder(0)
print()
print('Inorder')
tree.inorder(0)
print()
print('Postorder')
tree.postorder(0)

Submission status: Wrong Answer

Solution code:
print("Preorder")
print(" 3 4 0 1 2")
print("Inorder")
print(" 4 3 1 0 2")
print("Postorder")
print(" 4 1 2 0 3")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
def Pre(i):
    if dali[i].node != -1:
        ret = dali[i].node
        dali[i].node = -1
        order.append(ret)
    if dali[i].left != -1:
        Pre(dali[i].left)
    if dali[i].right != -1:
        Pre(dali[i].right)
def Pre2(u):
    if u == -1:
        return 
    order.append(u)
    Pre2(dali[u].left)
    Pre2(dali[u].right)
def In(i):
    if dali2[i].left != -1:
        In(dali2[i].left)
    if dali2[i].node != -1:
        
        ret = dali2[i].node
        dali2[i].node = -1
        order.append(ret)
    if dali2[i].right != -1:
        In(dali2[i].right)
def In2(u):
    if u == -1:
        return 
    In2(dali2[u].left)
    
    order.append(u)
    In2(dali2[u].right)


def Postorder(u):
    if u == -1:
        return None
    Postorder(dali3[u].left)
    Postorder(dali3[u].right)
    order.append(dali3[u].node)
    dali3[u].node = -1



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


def inputdata(i):
    node, left, right = list(map(int, input().split()))
    dali[node] = BiTree(node, left, right)
    dali2[node] = BiTree(node, left, right)
    dali3[node] = BiTree(node, left, right)
def getParent(i):
    for k in range(n):
        if(dali[k].right == dali[i].node) or (dali[k].left == dali[i].node):
            dali[i].parent = dali[k].node
            return dali[i].parent
    dali[i].parent = -1
def getParent3(i):
    for k in range(n):
        if(dali3[k].right == dali3[i].node) or (dali3[k].left == dali3[i].node):
            dali3[i].parent = dali3[k].node
            return dali3[i].parent
    dali3[i].parent = -1
# Getting Root
        

n = int(input())
dali = [0] * n
dali2 = [0] * n
dali3 = [0] * n
order = []
for i in range(n):
    inputdata(i)
    """
for i in range(n):
    Pre(dali[i].node)
"""
for i in range(n):
    for j in range(n):
        if i == dali[j].left or i == dali[j].right:
            break
    if j == n-1:
        root = i
        break


order = []
for i in range(n):
    getParent(dali2[i].node)
for i in range(n):
    getParent(dali[i].node)
for i in range(n):
    getParent3(dali3[i].node)
Pre2(root)
print("Preoeder")
print(" ",end = "")
print(*order)
order = []

In2(root)
print("Inorder")
print(" ",end = "")
print(*order)

order = []
print("Postorder")
print(" ",end = "")
Postorder(root)
print(*order)

Submission status: Wrong Answer

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

root = None
n = int(input())
node_list = []
for i in range(n):
    node_list.append(Node(i))

for i in range(n):
    id, left, right = list(map(int, input().split()))
    node = node_list[id]
    if left > -1:
        node.left = node_list[left]
    if right > -1:
        node.right = node_list[right]
    if id == 0:
        root = node

def preorder(node):
    if node is None:
        return
    print(' ' + str(node.id), end='')
    preorder(node.left)
    preorder(node.right)

def inorder(node):
    if node is None:
        return
    
    inorder(node.left)
    print(' ' + str(node.id), end='')
    inorder(node.right)

def postorder(node):
    if node is None:
        return
    print(' ' + str(node.id), end='')
    postorder(node.left)
    postorder(node.right)

print('Preorder')
preorder(root)
print('')

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

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

Submission status: Wrong Answer

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

root = None
n = int(input())
node_list = []
for i in range(n):
    node_list.append(Node(i))

for i in range(n):
    id, left, right = list(map(int, input().split()))
    node = node_list[id]
    if left > -1:
        node_list[left].parent = node
        node.left = node_list[left]
    if right > -1:
        node_list[right].parent = node
        node.right = node_list[right]

root = None
for node in node_list:
    if node.parent is None:
        root = node
        break

def preorder(node):
    if node is None:
        return
    print(' ' + str(node.id), end='')
    preorder(node.left)
    preorder(node.right)

def inorder(node):
    if node is None:
        return
    
    inorder(node.left)
    print(' ' + str(node.id), end='')
    inorder(node.right)

def postorder(node):
    if node is None:
        return
    print(' ' + str(node.id), end='')
    postorder(node.left)
    postorder(node.right)

print('Preorder')
preorder(root)
print('')

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

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

Submission status: Wrong Answer

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
        self.nodes[-1] = None
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id], self.nodes[right_id])
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = self.left = self.right = None
        self.depth = self.height = 0

    def add_child(self, left, right):
        self.left = left
        self.right = right
        
        self.update_height()
        
        for child in self.children():
            child.parent = self
            child.update_depth()
    def update_height(self):
        if self.degree():
            self.height = max([child.height + 1 for child in self.children()])
            if self.parent:
                self.parent.update_height()
            
    def update_depth(self):
        self.depth = self.parent.depth + 1
        for child in self.children():
            child.update_depth()
                
    def nodetype(self):
        if self.parent:
            if self.degree():
                return 'internal node'
            else:
                return 'leaf'
        else:
            return 'root'
    def degree(self):
        return len(self.children())
    
    def children(self):
        return [child for child in [self.left, self.right] if child]
    
    def sibling(self):
        if self.parent and self.parent.degree() == 2:
            if self.parent.left == self:
                return self.parent.right.id
            else:
                return self.parent.left.id
        else:
            return -1

    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id,
            self.parent.id if self.parent else - 1,
            self.sibling(),
            self.degree(),
            self.depth,
            self.height,
            self.nodetype())
    def walk(self, order):
        orders = {'Preorder':[self, self.left, self.right], 'Inorder':[self.left, self, self.right], 'Postorder':[self.left, self.right, self]}
        
        for node in orders[order]:
            if node == self:
                yield node
            elif node:
                for childnode in node.walk(order):
                    yield childnode
                
tree = Tree()

n = int(input())
for i in range(n):
    id, left, right = map(int, input().split())
    tree.add_child(id, left, right)
orders = ['Preorder', 'Inorder', 'Postorder']

for order in orders:
    print(order)
    print(*[node.id for node in tree.nodes[0].walk(order)])

Submission status: Wrong Answer

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
        self.nodes[-1] = None
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id], self.nodes[right_id])
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = self.left = self.right = None
        self.depth = self.height = 0

    def add_child(self, left, right):
        self.left = left
        self.right = right
        
        self.update_height()
        
        for child in self.children():
            child.parent = self
            child.update_depth()
    def update_height(self):
        if self.degree():
            self.height = max([child.height + 1 for child in self.children()])
            if self.parent:
                self.parent.update_height()
            
    def update_depth(self):
        self.depth = self.parent.depth + 1
        for child in self.children():
            child.update_depth()
                
    def nodetype(self):
        if self.parent:
            if self.degree():
                return 'internal node'
            else:
                return 'leaf'
        else:
            return 'root'
    def degree(self):
        return len(self.children())
    
    def children(self):
        return [child for child in [self.left, self.right] if child]
    
    def sibling(self):
        if self.parent and self.parent.degree() == 2:
            if self.parent.left == self:
                return self.parent.right.id
            else:
                return self.parent.left.id
        else:
            return -1

    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id,
            self.parent.id if self.parent else - 1,
            self.sibling(),
            self.degree(),
            self.depth,
            self.height,
            self.nodetype())
    def walk(self, order):
        orders = {'Preorder':[self, self.left, self.right], 'Inorder':[self.left, self, self.right], 'Postorder':[self.left, self.right, self]}
        
        for node in orders[order]:
            if node == self:
                yield node
            elif node:
                for childnode in node.walk(order):
                    yield childnode
                
tree = Tree()

n = int(input())
for i in range(n):
    id, left, right = map(int, input().split())
    tree.add_child(id, left, right)
orders = ['Preorder', 'Inorder', 'Postorder']

for order in orders:
    print(order)
    print('', *[node.id for node in tree.nodes[0].walk(order)])

Submission status: Wrong Answer

Solution code:
from collections import namedtuple

class TreeWalk:
    def __init__(self, t):
        self.t = t

    def preParse(self, u):
        if u == -1:
            return 
        print(" ", str(u), end = "")
        self.preParse(self.t[u].l)
        self.preParse(self.t[u].r)

    def inParse(self, u):
        if u == -1:
            return 
        self.inParse(self.t[u].l)
        print(" ", str(u), end = "")
        self.inParse(self.t[u].r)

    def postParse(self, u):
        if u == -1:
            return 
        self.inParse(self.t[u].l)
        self.inParse(self.t[u].r)
        print(" ", str(u), end = "")
    
if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    root = -1
    for i in range(n):
        v, l, r = [int(i) for i in input().rstrip().split(" ")]
        t[v] = t[v]._replace(l = l, r = r)
        if l != -1:
            t[l] = t[l]._replace(p = v)
        if r != -1:
            t[r] = t[r]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            root = i

    x = TreeWalk(t)
    print("Preorder")
    x.preParse(root)
    print()
    print("Inorder")
    x.inParse(root)
    print()
    print("Postorder")
    x.postParse(root)
    print()

Submission status: Wrong Answer

Solution code:
from collections import namedtuple

class TreeWalk:
    def __init__(self, t):
        self.t = t

    def preParse(self, u):
        if u == -1:
            return 
        print(" ", str(u), end = "")
        self.preParse(self.t[u].l)
        self.preParse(self.t[u].r)

    def inParse(self, u):
        if u == -1:
            return 
        self.inParse(self.t[u].l)
        print(" ", str(u), end = "")
        self.inParse(self.t[u].r)

    def postParse(self, u):
        if u == -1:
            return 
        self.inParse(self.t[u].l)
        self.inParse(self.t[u].r)
        print(" ", str(u), end = "")
    
if __name__ == '__main__':
    n = int(input().rstrip())
    Node = namedtuple('Node', ['p', 'l', 'r'])
    t = [Node(-1, -1, -1)] * n
    root = -1
    for i in range(n):
        v, l, r = [int(i) for i in input().rstrip().split(" ")]
        t[v] = t[v]._replace(l = l, r = r)
        if l != -1:
            t[l] = t[l]._replace(p = v)
        if r != -1:
            t[r] = t[r]._replace(p = v)
    for i in range(n):
        if (t[i].p == -1):
            root = i

    x = TreeWalk(t)
    print("Preorder")
    x.preParse(root)
    print()
    print("Inorder")
    x.inParse(root)
    print()
    print("Postorder")
    x.postParse(root)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def pre_order(id, list):
    if id > -1:
        list.append(id)
        pre_order(node_dic[id].left, list)
        pre_order(node_dic[id].right, list)

def in_order(id, list):
    if id > -1:
        in_order(node_dic[id].left, list)
        list.append(id)
        in_order(node_dic[id].right, list)

def post_order(id, list):
    if id > -1:
        post_order(node_dic[id].left, list)
        post_order(node_dic[id].right, list)
        list.append(id)

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

n = int(raw_input())
node_dic = {}
root = 0
for i in range(n):
    id, left, right = map(int, raw_input().split())
    node_dic[id] = Node_Class(left, right)
for i in range(n):
    if left > -1:
        root -= left
    if right > -1:
        root -= right
A = []
B = []
C = []
pre_order(root, A)
in_order(root, B)
post_order(root, C)
print "Preorder"
print " "+" ".join(map(str, A))
print "Inorder"
print " "+" ".join(map(str, B))
print "Postorder"
print " "+" ".join(map(str, C))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def pre_order(id, list):
    if id > -1:
        list.append(id)
        pre_order(node_dic[id].left, list)
        pre_order(node_dic[id].right, list)

def in_order(id, list):
    if id > -1:
        in_order(node_dic[id].left, list)
        list.append(id)
        in_order(node_dic[id].right, list)

def post_order(id, list):
    if id > -1:
        post_order(node_dic[id].left, list)
        post_order(node_dic[id].right, list)
        list.append(id)

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

n = int(raw_input())
node_dic = {}
root = 0
for i in range(n):
    id, left, right = map(int, raw_input().split())
    node_dic[id] = Node_Class(left, right)
    root += i
for i in range(n):
    if left > -1:
        root -= left
    if right > -1:
        root -= right
A = []
B = []
C = []
pre_order(root, A)
in_order(root, B)
post_order(root, C)
print "Preorder"
print " "+" ".join(map(str, A))
print "Inorder"
print " "+" ".join(map(str, B))
print "Postorder"
print " "+" ".join(map(str, C))

Submission status: Wrong Answer

Solution code:
from collections import namedtuple
Node = namedtuple('Node', ['parent', 'children'])
  
class my_binary_tree:
    def __init__(self, N=[]):
        self.T = {}
        for ni in N: self.addNode(ni)
  
    def addNode(self, n):
        p = self.T.get(n[0],Node(-1,[-1,-1])).parent
        self.T[n[0]] = Node(p,n[1:])
        for c in n[1:]:
            if c > -1:  
                cc = self.T.get(c,Node(-1,[-1,-1])).children
                self.T[c] = Node(n[0],cc)
  
    def getParent(self, i): return self.T[i].parent
  
    def getChildren(self, i): return self.T[i].children
  
    def getDepth(self, i):
        if self.T[i].parent == -1: return 0
        return self.getDepth(self.T[i].parent) + 1
  
    def getHeight(self, i):
        c0 = self.T[i].children[0]
        c1 = self.T[i].children[1]
        if c0 + c1 == -2: return 0
        return max( ( 0 if c0 == -1 else self.getHeight(c0) ), \
                    ( 0 if c1 == -1 else self.getHeight(c1) ) )\
               + 1
  
    def getDegree(self, i):
        return int(self.T[i].children[0] != -1) + \
               int(self.T[i].children[1] != -1)
  
    def getNodeType(self, i):
        if self.T[i].parent == -1        : return 'root'
        if sum(self.T[i].children) == -2 : return 'leaf'
        return 'internal node'
  
    def getSibling(self, i):
        p = self.T[i].parent
        if p == -1: return -1
        return sum(self.T[p].children) - i
  
    def getIdList(self): return sorted(self.T.keys())
  
    def getPreorderList(self, L=[], i=0):
        c0 = self.T[i].children[0]
        c1 = self.T[i].children[1]
        L.append(i)
        if c0 != -1: self.getPreorderList(L, c0)
        if c1 != -1: self.getPreorderList(L, c1)
        return L
  
    def getInorderList(self, L=[], i=0):
        c0 = self.T[i].children[0]
        c1 = self.T[i].children[1]
        if c0 != -1: self.getInorderList(L, c0)
        L.append(i)
        if c1 != -1: self.getInorderList(L, c1)
        return L
  
    def getPostorderList(self, L=[], i=0):
        c0 = self.T[i].children[0]
        c1 = self.T[i].children[1]
        if c0 != -1: self.getPostorderList(L, c0)
        if c1 != -1: self.getPostorderList(L, c1)
        L.append(i)
        return L
  
   
if __name__=='__main__':
    n = int(input())
    N = [None]*n
    for i in range(n): N[i] = list(map(int,input().split()))
    tree = my_binary_tree(N)
       
    print("Preorder")
    print("",*tree.getPreorderList())
    print("Inorder")
    print("",*tree.getInorderList())
    print("Postorder")
    print("",*tree.getPostorderList())

Submission status: Wrong Answer

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

def inorder(n):
    if n != None:
        inorder(n.left)
        print n.v,
        inorder(n.right)

def preorder(n):
    if n != None:
        print n.v,
        preorder(n.left)
        preorder(n.right)

def postorder(n):
    if n != None:
        postorder(n.left)
        postorder(n.right)
        print n.v,

def set_node(n,nodes,nid):
    if nodes[nid][0] != -1:
        n.left = set_node(Node(nodes[nid][0]),nodes,nodes[nid][0])
    if nodes[nid][1] != -1:
        n.right = set_node(Node(nodes[nid][1]),nodes,nodes[nid][1])
    return n

n = int(raw_input())
nodes = {}
for _ in range(n):
    nid,left,right = map(int,raw_input().split(' '))
    nodes[nid] = (left,right)

tree = Node(0)
tree = set_node(tree,nodes,0)

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

Submission status: Wrong Answer

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

def inorder(n):
    if n != None:
        inorder(n.left)
        print n.v,
        inorder(n.right)

def preorder(n):
    if n != None:
        print n.v,
        preorder(n.left)
        preorder(n.right)

def postorder(n):
    if n != None:
        postorder(n.left)
        postorder(n.right)
        print n.v,

def set_node(n,nodes,nid):
    if nodes[nid][0] != -1:
        n.left = set_node(Node(nodes[nid][0]),nodes,nodes[nid][0])
    if nodes[nid][1] != -1:
        n.right = set_node(Node(nodes[nid][1]),nodes,nodes[nid][1])
    return n

n = int(raw_input())
nodes = {}
root = -1
for _ in range(n):
    nid,left,right = map(int,raw_input().split(' '))
    if root == -1:
        root = nid
    nodes[nid] = (left,right)

tree = Node(root)
tree = set_node(tree,nodes,root)

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

Submission status: Wrong Answer

Solution code:
def preorder(i):
    if i == -1:
        return ""
    n = T[i]
    l = n[1]
    ls = preorder(l)
    r = n[2]
    rs = preorder(r)
    ans = " {}".format(i)
    if ls != "":
        ans += ls
    if rs != "":
        ans += rs

    return ans

def inorder(i):
    if i == -1:
        return ""
    n = T[i]
    l = n[1]
    ls = inorder(l)
    r = n[2]
    rs = inorder(r)
    ans = " {}".format(i)
    if ls != "":
        ans = ls + ans
    if rs != "":
        ans += rs

    return ans

def postorder(i):
    if i == -1:
        return ""
    n = T[i]
    l = n[1]
    ls = postorder(l)
    r = n[2]
    rs = postorder(r)
    ans = ""
    if ls != "":
        ans = ls
    if rs != "":
        ans += rs
    ans += " {}".format(i)

    return ans

n = int(input())
root = set([x for x in range(n)])

T = [None] * n
for x in range(n):
    N = list(map(int, input().split()))
    T[x] = N
    root -= set(N[1:])

r = root.pop()

print("Preorder")
print(preorder(r))

print("Inorder")
print(inorder(r))

print("Postorder")
print(postorder(r))

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C&lang=jp
import time
def preorder(binary_tree, target_index, result):

    result.append(target_index)
    
    left = binary_tree[target_index]["left"]
    right = binary_tree[target_index]["right"]
    if not left == -1:
        preorder(binary_tree, left, result)
    if not right == -1:
        preorder(binary_tree, right, result)

def inorder(binary_tree, target_index, result):
    
    left = binary_tree[target_index]["left"]
    right = binary_tree[target_index]["right"]
    
    if not left == -1:
        inorder(binary_tree, left, result)
    
    result.append(target_index)
    
    if not right == -1:
        inorder(binary_tree, right, result)

def postorder(binary_tree, target_index, result):
    
    left = binary_tree[target_index]["left"]
    right = binary_tree[target_index]["right"]
    
    if not left == -1:
        postorder(binary_tree, left, result)
    if not right == -1:
        postorder(binary_tree, right, result)

    result.append(target_index)
    
def make_binary_tree(node_data, node_num):
    binary_tree = [{"left":-1, "right":-1} for a in range(node_num)]
    root_index = sum([i for i in range(node_num)])

    for node in node_data:
        binary_tree[node[0]]["left"] =  node[1]
        binary_tree[node[0]]["right"] =  node[2]

        if not node[1] == -1:
            root_index -= node[1]
        if not node[2] == -1:
            root_index -= node[2]

    return root_index, binary_tree

def main():
    node_num = int(input())
    node_data = [[int(a) for a in input().split()] for i in range(node_num)]
    root_index, binary_tree = make_binary_tree(node_data, node_num)
    
    preorder_list = []
    preorder(binary_tree, root_index, preorder_list)
    print("Preorder\n", *preorder_list)
    inorder_list = []
    inorder(binary_tree, root_index, inorder_list)
    print("Inorder\n", *inorder_list)
    postorder_list = []
    postorder(binary_tree, root_index, postorder_list)
    print("Inorder\n", *postorder_list)
if __name__ == "__main__":
    main()