트리 ADT 구현 = dict

dict, (l, r)

import sys
input = sys.stdin.readline

N = int(input())
    
tree = {}
for _ in range(N):
    v, l, r = input().split()
    tree[v] = (l, r)

def preorder(v):
    l, r = tree[v]
    print(v, end='')
    if l != '.':
        preorder(l)
    if r != '.':
        preorder(r)
def inorder(v):
    l, r = tree[v]
    if l != '.':
        inorder(l)
    print(v, end='')
    if r != '.':
        inorder(r)
def postorder(v):
    l, r = tree[v]
    if l != '.':
        postorder(l)
    if r != '.':
        postorder(r)
    print(v, end='')

preorder('A')
print()
inorder('A')
print()
postorder('A')

dict, class Node():

class Node():
    def __init__(self, v, l, r):
        self.v = v
        self.l = l
        self.r = r

tree = {}
for _ in range(N):
    v, l, r = input().split()
    tree[v] = Node(v, l, r)
    
def preorder(c):
    node = tree[c]
    print(node.v, end='')
    if node.l != '.':
        preorder(node.l)
    if node.r != '.':
        preorder(node.r)
    
def inorder(c):
    node = tree[c]
    if node.l != '.':
        inorder(node.l)
    print(node.v, end='')
    if node.r != '.':
        inorder(node.r)

def postorder(c):
    node = tree[c]
    if node.l != '.':
        postorder(node.l)
    if node.r != '.':
        postorder(node.r)
    print(node.v, end='')