https://www.acmicpc.net/problem/1991
import sys
def pre_traversal(node):
print(node,end='')
left_node, right_node = tree[node]
if left_node != '.':
pre_traversal(left_node)
if right_node != '.':
pre_traversal(right_node)
def in_traversal(node):
left_node, right_node = tree[node]
if left_node != '.':
in_traversal(left_node)
print(node,end='')
if right_node != '.':
in_traversal(right_node)
def post_traversal(node):
left_node, right_node = tree[node]
if left_node != '.':
post_traversal(left_node)
if right_node != '.':
post_traversal(right_node)
print(node,end='')
n = int(input())
tree = {}
for _ in range(n):
comp = sys.stdin.readline().split()
tree.setdefault(comp[0],comp[1:])
pre_traversal('A')
print('')
in_traversal('A')
print('')
post_traversal('A')