Description

Given a binary tree, output its preorder traversal.

Input Format

The first line contains the number of nodes $n$ ($1 \leq n \leq 26$).

Each of the next $n$ lines contains three characters: the first character is the node, and the next two characters are its left and right children, respectively. In particular, the testdata guarantees that the node appearing on the first of these $n$ lines is the root node.

A null child is denoted by *.

Output Format

The preorder traversal of the binary tree.

6
abc
bdi
cj*
d**
i**
j**

abdicj

Hint

Translated by ChatGPT 5