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: WA: Presentation Error

Solution code:
def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_cn = map(int,raw_input().split())
        id_node = id_cn.pop(0)
        
        tree.add(id_node,None,id_cn)
    
    tree.search_children()
    tree.set_depth_height(tree.nodes[tree.id_root],0)

    print "Preorder"
    print "",
    tree.preorder(tree.nodes[tree.id_root])
    print ""
    print "Inorder"
    print "",
    tree.inorder(tree.nodes[tree.id_root])
    print ""
    print "Postorder"
    print "",
    tree.postorder(tree.nodes[tree.id_root])

    
class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [MyNode() for i in range(num_nodes)]
        self.id_root = None

    def add(self,id_node,id_parent,id_children):
        node = self.nodes[id_node]
        node.id_self = id_node
        node.id_parent = id_parent
        node.id_children = id_children
    
    def search_children(self):
        for node in self.nodes:
            if all(item==-1 for item in node.id_children):
                node.node_type = "leaf"
                node.degree = 0
            else:
                node.node_type = "internal node"
                l = node.id_children[0]
                r = node.id_children[1]
                if l == -1:
                    node.degree = 1
                    self.nodes[r].id_parent = node.id_self
                    self.nodes[r].sibling = l
                elif r == -1:
                    node.degree = 1
                    self.nodes[l].id_parent = node.id_self
                    self.nodes[l].sibling = r
                else:
                    node.degree = 2
                    self.nodes[l].id_parent = node.id_self
                    self.nodes[r].id_parent = node.id_self
                    self.nodes[l].sibling = r
                    self.nodes[r].sibling = l

        for node in self.nodes:
            if node.id_parent == None:
                node.id_parent = -1
                node.node_type = "root"
                self.id_root = node.id_self
                break

    def set_depth_height(self,node,depth):
        node.depth = depth
        l_height = []
        if all(item==-1 for item in node.id_children):
            node.height = 0
            return 0
        else:
            for item in node.id_children:
                if not item == -1:
                    l_height.append(self.set_depth_height(self.nodes[item],depth+1))
            height = max(l_height)+1
            node.height = height
            return height

    def preorder(self,node):
        print node.id_self,
        l,r = node.id_children
        if not l == -1:
            self.preorder(self.nodes[l])
        if not r == -1:
            self.preorder(self.nodes[r])    

    def inorder(self,node):
        l,r = node.id_children
        if not l == -1:
            self.inorder(self.nodes[l])
        print node.id_self,
        if not r == -1:
            self.inorder(self.nodes[r])

    def postorder(self,node):
        l,r = node.id_children
        if not l == -1:
            self.postorder(self.nodes[l])
        if not r == -1:
            self.postorder(self.nodes[r])
        print node.id_self,
                


class MyNode():
    def __init__(self):
        self.id_self = None
        self.id_parent = None
        self.id_children = None
        self.depth = None
        self.node_type = None
        self.n_children = 0
        self.sibling = -1
        self.degree = 0
        self.height = 0


if __name__ == "__main__":
    main()

Submission status: WA: Presentation Error

Solution code:
import sys

def main():
    n = input()
    tree = MyTree(n)
    for i in range(n):
        id_cn = map(int,raw_input().split())
        id_node = id_cn.pop(0)
        
        tree.add(id_node,None,id_cn)
    
    tree.search_children()
    tree.set_depth_height(tree.nodes[tree.id_root],0)

    print "Preorder"
    tree.preorder(tree.nodes[tree.id_root])
    print ""
    print "Inorder"
    tree.inorder(tree.nodes[tree.id_root])
    print ""
    print "Postorder"
    tree.postorder(tree.nodes[tree.id_root])

    
class MyTree():
    def __init__(self,num_nodes):
        self.nodes = [MyNode() for i in range(num_nodes)]
        self.id_root = None

    def add(self,id_node,id_parent,id_children):
        node = self.nodes[id_node]
        node.id_self = id_node
        node.id_parent = id_parent
        node.id_children = id_children
    
    def search_children(self):
        for node in self.nodes:
            if all(item==-1 for item in node.id_children):
                node.node_type = "leaf"
                node.degree = 0
            else:
                node.node_type = "internal node"
                l = node.id_children[0]
                r = node.id_children[1]
                if l == -1:
                    node.degree = 1
                    self.nodes[r].id_parent = node.id_self
                    self.nodes[r].sibling = l
                elif r == -1:
                    node.degree = 1
                    self.nodes[l].id_parent = node.id_self
                    self.nodes[l].sibling = r
                else:
                    node.degree = 2
                    self.nodes[l].id_parent = node.id_self
                    self.nodes[r].id_parent = node.id_self
                    self.nodes[l].sibling = r
                    self.nodes[r].sibling = l

        for node in self.nodes:
            if node.id_parent == None:
                node.id_parent = -1
                node.node_type = "root"
                self.id_root = node.id_self
                break

    def set_depth_height(self,node,depth):
        node.depth = depth
        l_height = []
        if all(item==-1 for item in node.id_children):
            node.height = 0
            return 0
        else:
            for item in node.id_children:
                if not item == -1:
                    l_height.append(self.set_depth_height(self.nodes[item],depth+1))
            height = max(l_height)+1
            node.height = height
            return height

    def preorder(self,node):
        sys.stdout.write(" {}".format(node.id_self))
        l,r = node.id_children
        if not l == -1:
            self.preorder(self.nodes[l])
        if not r == -1:
            self.preorder(self.nodes[r])    

    def inorder(self,node):
        l,r = node.id_children
        if not l == -1:
            self.inorder(self.nodes[l])
        sys.stdout.write(" {}".format(node.id_self))
        if not r == -1:
            self.inorder(self.nodes[r])

    def postorder(self,node):
        l,r = node.id_children
        if not l == -1:
            self.postorder(self.nodes[l])
        if not r == -1:
            self.postorder(self.nodes[r])
        sys.stdout.write(" {}".format(node.id_self))
                


class MyNode():
    def __init__(self):
        self.id_self = None
        self.id_parent = None
        self.id_children = None
        self.depth = None
        self.node_type = None
        self.n_children = 0
        self.sibling = -1
        self.degree = 0
        self.height = 0


if __name__ == "__main__":
    main()

Submission status: WA: Presentation Error

Solution code:
import sys

I = 0
L = 1
R = 2
P = 3
B = 4
D = 5
H = 6

def getroot(A, id):
    if A[id][P] > -1:
        return getroot(A,A[id][P])
    return A[id][I]

def preorder(N,id,A):
    if id < 0:
        return
    A.append(id)
    preorder(N,N[id][L],A)
    preorder(N,N[id][R],A)

def inorder(N,id,A):
    if id < 0:
        return
    inorder(N,N[id][L],A)
    A.append(id)
    inorder(N,N[id][R],A)

def postorder(N,id,A):
    if id < 0:
        return
    postorder(N,N[id][L],A)
    postorder(N,N[id][R],A)
    A.append(id)


def main():

    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    nlist = list(istr.splitlines())
    
    nodes = [[i, -1, -1, -1, -1, 0, 0] for i in range(num)]

    for nstr in nlist:
        i = list(map(int,nstr.split()))
        n = nodes[i[I]]
        n[I] = i[I]
        if i[L] > -1:
            n[L] = i[L]
            nodes[n[L]][P] = i[I]
            nodes[n[L]][B] = i[R]
        if i[R] > -1:
            n[R] = i[R]
            nodes[n[R]][P] = i[I]
            nodes[n[R]][B] = i[L]
#        print("set n:{} {} {}".format(n[I],n,i))

    r = getroot(nodes, 0)
#    setd(nodes,r, 0)

    pre = []
    ino = []
    pos = []

    preorder(nodes,r,pre)
    inorder(nodes,r,ino)
    postorder(nodes,r,pos)

    print("Preorder")
    print(" ".join(map(str,pre)))
    print("Inorder")
    print(" ".join(map(str,ino)))
    print("Postorder")
    print(" ".join(map(str,pos)))
if __name__ == '__main__':
    main()

Submission status: WA: Presentation Error

Solution code:
class Node:
    def __init__(self, nid):
        self.nid = nid
        self.l = None
        self.r = None

def preorder(T):
    ret = [T.nid]
    if T.l != None:
        ret += preorder(T.l)
    if T.r != None:
        ret += preorder(T.r)
    return ret

def inorder(T):
    ret = []
    if T.l != None:
        ret += inorder(T.l)
    ret.append(T.nid)
    if T.r != None:
        ret += inorder(T.r)
    return ret

def postorder(T):
    ret = []
    if T.l != None:
        ret += postorder(T.l)
    if T.r != None:
        ret += postorder(T.r)
    ret.append(T.nid)
    return ret



n = int(raw_input())
nodes = {}
T = None
for _ in range(n):
    nid, lid, rid = raw_input().split(' ')
    if not nid in nodes:
        node = Node(nid)
        nodes[nid] = node
    if lid != '-1':
        if not lid in nodes:
            l = Node(lid)
            nodes[lid] = l
        nodes[nid].l = nodes[lid]
    if rid != '-1':
        if not rid in nodes:
            r = Node(rid)
            nodes[rid] = r
        nodes[nid].r = nodes[rid]
    if T == None:
        T = nodes[nid]

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

Submission status: WA: Presentation Error

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print("",self.node_id, end="")
        if l != -1:
            tree[l].pre_order_search()
        if r != -1:
            tree[r].pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].in_order_search()
        print("",self.node_id, end="")
        if r != -1:
            tree[r].in_order_search()

    def post_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].post_order_search()
        if r != -1:
            tree[r].post_order_search()
        print("",self.node_id, end="")

n = int(input())
tree = [None for i in range(n)]
root_set = set(range(n))

for i in range(n):
    node_id, left, right = map(int, input().split())
    tree[node_id] = Node(node_id, left, right)
    root_set -= set([left, right])
root = root_set.pop()
print("Preorder")
tree[root].pre_order_search()
print("\nInorder")
tree[root].in_order_search()
print("\nPostorder")
tree[root].post_order_search()

Submission status: WA: Presentation Error

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print("",self.node_id, end="")
        if l != -1:
            tree[l].pre_order_search()
        if r != -1:
            tree[r].pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].in_order_search()
        print("",self.node_id, end="")
        if r != -1:
            tree[r].in_order_search()

    def post_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].post_order_search()
        if r != -1:
            tree[r].post_order_search()
        print("",self.node_id, end="")

n = int(input())
tree = [None for i in range(n)]
root_set = set(range(n))

for i in range(n):
    node_id, left, right = map(int, input().split())
    tree[node_id] = Node(node_id, left, right)
    root_set -= set([left, right])
root = root_set.pop()
print("Preorder")
tree[root].pre_order_search()
print("\nInorder")
tree[root].in_order_search()
print("\nPostorder")
tree[root].post_order_search()
print("\n")

Submission status: WA: Presentation Error

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print(" " + str(self.node_id), end="")
        if l != -1:
            tree[l].pre_order_search()
        if r != -1:
            tree[r].pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].in_order_search()
        print(" " + str(self.node_id), end="")
        if r != -1:
            tree[r].in_order_search()

    def post_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].post_order_search()
        if r != -1:
            tree[r].post_order_search()
        print(" " + str(self.node_id), end="")

n = int(input())
tree = [None for i in range(n)]
root_set = set(range(n))

for i in range(n):
    node_id, left, right = map(int, input().split())
    tree[node_id] = Node(node_id, left, right)
    root_set -= set([left, right])
root = root_set.pop()
print("Preorder")
tree[root].pre_order_search()
print("\nInorder")
tree[root].in_order_search()
print("\nPostorder")
tree[root].post_order_search()
print("\n")

Submission status: WA: Presentation Error

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print(" " + str(self.node_id), end="")
        if l != -1:
            tree[l].pre_order_search()
        if r != -1:
            tree[r].pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].in_order_search()
        print(" " + str(self.node_id), end="")
        if r != -1:
            tree[r].in_order_search()

    def post_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].post_order_search()
        if r != -1:
            tree[r].post_order_search()
        print(" " + str(self.node_id), end="")

n = int(input())
tree = [None for i in range(n)]
root_set = set(range(n))

for i in range(n):
    node_id, left, right = map(int, input().split())
    tree[node_id] = Node(node_id, left, right)
    root_set -= set([left, right])
root = root_set.pop()
print("Preorder")
tree[root].pre_order_search()
print("\nInorder")
tree[root].in_order_search()
print("\nPostorder")
tree[root].post_order_search()

Submission status: WA: Presentation Error

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print("",self.node_id, end="")
        if l != -1:
            tree[l].pre_order_search()
        if r != -1:
            tree[r].pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].in_order_search()
        print("",self.node_id, end="")
        if r != -1:
            tree[r].in_order_search()

    def post_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].post_order_search()
        if r != -1:
            tree[r].post_order_search()
        print("",self.node_id, end="")

n = int(input())
tree = [None for i in range(n)]
root_set = set(range(n))

for i in range(n):
    node_id, left, right = map(int, input().split())
    tree[node_id] = Node(node_id, left, right)
    root_set -= set([left, right])
root = root_set.pop()
print("Preorder")
tree[root].pre_order_search()
print("\r\nInorder")
tree[root].in_order_search()
print("\r\nPostorder")
tree[root].post_order_search()
print("\r\n")

Submission status: WA: Presentation Error

Solution code:
from collections import defaultdict
def preorder(here, conn, chain):
    if here == -1:
        return
    chain.append(here)
    if conn[here]:
        preorder(conn[here][0], conn, chain)
        preorder(conn[here][1], conn, chain)

def inorder(here, conn, chain):
    if here == -1:
        return
    if conn[here]:
        inorder(conn[here][0], conn, chain)
        chain.append(here)
        inorder(conn[here][1], conn, chain)

def postorder(here, conn, chain):
    if here == -1:
        return
    if conn[here]:
        postorder(conn[here][0], conn, chain)
        postorder(conn[here][1], conn, chain)
    chain.append(here)

query = int(input())
connect = defaultdict(list)
in_v = [0 for n in range(query + 1)]
for _ in range(query):
    here, left, right = (int(n) for n in input().split(" "))
    connect[here] = [left, right]
    in_v[left] += 1
    in_v[right] += 1
for i in range(query):
    if not in_v[i]:
        root = i
        break
preo = []
ino = []
posto = []
preorder(root, connect, preo)
inorder(root, connect, ino)
postorder(root, connect, posto)

print("Preorder")
print(*preo)
print("Inorder")
print(*ino)
print("Postorder")
print(*posto)

Submission status: WA: Presentation Error

Solution code:
n = int(input())
left = [None for i in range(n)]
right = [None for i in range(n)]
root = sum(range(n)) - n - 1

for i in range(n):
    i, l, r = map(int, input().split())
    left[i] = l
    right[i] = r
    root -= (l + r)

def Preorder(i):
    if i == -1:
        return
    print(" {}".format(i), end = "")
    Preorder(left[i])
    Preorder(right[i])

def Inorder(i):
    if i == -1:
        return
    Inorder(left[i])
    print(" {}".format(i), end = "")
    Inorder(right[i])

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

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

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

print("Postorder")
Postorder(root)
print

Submission status: WA: Presentation Error

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

import sys
sys.setrecursionlimit(100000)

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

def preParse(u, res):
    if u == -1:
        return
    res.append(u)
    preParse(T[u].left, res)
    preParse(T[u].right, res)
    
def inParse(u, res):
    if u == -1:
        return
    inParse(T[u].left, res)
    res.append(u)
    inParse(T[u].right, res)
    
def postParse(u, res):
    if u == -1:
        return
    postParse(T[u].left, res)
    postParse(T[u].right, res)
    res.append(u)
    
    
if __name__ == '__main__':

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

    for _ in range(n):
        ID, left, right = list(map(int, input().split(" ")))
        T[ID].id = ID
        T[ID].left = left
        T[ID].right = right
        if left != -1:
            T[left].parent = ID
        if right != -1:
            T[right].parent = ID
    
    for node in T:
        if node.parent==-1:
            r = node.id
    res = []
    preParse(r, res)
    print("Preorder")
    print(" ".join(map(str, res)))
        
    res = []
    inParse(r, res)
    print("Inorder")
    print(" ".join(map(str, res)))
    
    res = []
    postParse(r, res)
    print("Postorder")
    print(" ".join(map(str, res)))

Submission status: WA: Presentation Error

Solution code:
class Tree:
    __slots__ = ['id', 'p', 'left', 'right', "type"]
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.left = -1
        self.right = -1
        self.type = "leaf"
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, left = {self.left}, right = {self.right}, type = {self.type}"
n = int(input())
tree = tuple(Tree(i) for i in range(n))
for _ in range(n):
    id, l, r = map(int, input().split())
    if l != -1:
        tree[id].left = l
        tree[l].p = id
    if r != -1:
        tree[id].right = r
        tree[r].p = id
root = 0
while tree[root].p != -1:
    root = tree[root].p
def preorder_tree_walk(id):
    print(f" {tree[id].id}", end="")
    if tree[id].left != -1:
        preorder_tree_walk(tree[id].left)
    if tree[id].right != -1:
        preorder_tree_walk(tree[id].right)
def inorder_tree_walk(id):
    if tree[id].left != -1:
        inorder_tree_walk(tree[id].left)
    print(f" {tree[id].id}", end="")
    if tree[id].right != -1:
        inorder_tree_walk(tree[id].right)
def postorder_tree_walk(id):
    if tree[id].left != -1:
        postorder_tree_walk(tree[id].left)
    if tree[id].right != -1:
        postorder_tree_walk(tree[id].right)
    print(f" {tree[id].id}", end="")
print("Preorder")
preorder_tree_walk(root)
print("\nInorder")
inorder_tree_walk(root)
print("\nPostorder")
postorder_tree_walk(root)

Submission status: WA: Presentation Error

Solution code:
import collections

nil = -1

def preParse(u):
    if u == nil:
        return None
    print(' {}'.format(u), end='')
    preParse(tree[u]['left'])
    preParse(tree[u]['right'])

def inParse(u):
    if u == nil:
        return None
    inParse(tree[u]['left'])
    print(' {}'.format(u), end='')
    inParse(tree[u]['right'])

def postParse(u):
    if u == nil:
        return None
    postParse(tree[u]['left'])
    postParse(tree[u]['right'])
    print(' {}'.format(u), end='')

if __name__ == '__main__':
    n = int(input())
    tree = collections.defaultdict(dict)
    roots = list()
    for _ in range(n):
        id_num, left, right = [int(x) for x in input().split()]
        tree[id_num]['left'] = left
        tree[id_num]['right'] = right
        if left != nil:
            tree[left]['parent'] = id_num
        if right != nil:
            tree[right]['parent'] = id_num
    
    for key, val in tree.items():
        if not 'parent' in tree[key]:
            roots.append(key)
    
    print('Preorder')
    preParse(roots[0])
    print()
    print('Inorder')
    inParse(roots[0])
    print()
    print('Postorder')
    postParse(roots[0])

Submission status: WA: Presentation Error

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')
    print(" ".join([str(node) for node in BinaryTree.preorder(tree)]))
    print('Inorder')
    print(" ".join([str(node) for node in BinaryTree.inorder(tree)]))
    print('Postorder')
    print(" ".join([str(node) for node in BinaryTree.postorder(tree)]))


if __name__ == '__main__':
    run()

Submission status: WA: Presentation Error

Solution code:
def pre_parse(node_id):
    if node_id == -1:
        return
    print(node_id, end=" ")
    pre_parse(node_info_list[node_id]['left'])
    pre_parse(node_info_list[node_id]['right'])


def in_parse(node_id):
    if node_id == -1:
        return
    in_parse(node_info_list[node_id]['left'])
    print(node_id, end=" ")
    in_parse(node_info_list[node_id]['right'])


def post_parse(node_id):
    if node_id == -1:
        return
    post_parse(node_info_list[node_id]['left'])
    post_parse(node_info_list[node_id]['right'])
    print(node_id, end=" ")


n = int(input())
node_info_list = [{
    'parent': -1,
    'left': -1,
    'right': -1,
} for _ in range(n)]

for _ in range(n):
    node_id, left, right = list(map(int, input().split()))
    node_info_list[node_id]['left'] = left
    node_info_list[node_id]['right'] = right
    node_info_list[left]['parent'] = node_id
    node_info_list[right]['parent'] = node_id

root_node_id = -1

for i in range(n):
    if node_info_list[i]['parent'] == -1:
        root_node_id = i
        break

print("Preorder")
pre_parse(root_node_id)
print("")
print("Inorder")
in_parse(root_node_id)
print("")
print("Postorder")
post_parse(root_node_id)

Submission status: WA: Presentation Error

Solution code:
def pre_parse(node_id):
    if node_id == -1:
        return
    print(" {0}".format(node_id), end="")
    pre_parse(node_info_list[node_id]['left'])
    pre_parse(node_info_list[node_id]['right'])


def in_parse(node_id):
    if node_id == -1:
        return
    in_parse(node_info_list[node_id]['left'])
    print(" {0}".format(node_id), end="")
    in_parse(node_info_list[node_id]['right'])


def post_parse(node_id):
    if node_id == -1:
        return
    post_parse(node_info_list[node_id]['left'])
    post_parse(node_info_list[node_id]['right'])
    print(" {0}".format(node_id), end="")


n = int(input())
node_info_list = [{
    'parent': -1,
    'left': -1,
    'right': -1,
} for _ in range(n)]

for _ in range(n):
    node_id, left, right = list(map(int, input().split()))
    node_info_list[node_id]['left'] = left
    node_info_list[node_id]['right'] = right
    node_info_list[left]['parent'] = node_id
    node_info_list[right]['parent'] = node_id

root_node_id = -1

for i in range(n):
    if node_info_list[i]['parent'] == -1:
        root_node_id = i
        break

print("Preorder")
pre_parse(root_node_id)
print("")
print("Inorder")
in_parse(root_node_id)
print("")
print("Postorder")
post_parse(root_node_id)

Submission status: WA: Presentation Error

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