Each input row gives a node and its left and right child. Labels are single uppercase letters, so an array indexed by label - 'A' stores both children. A missing child is written as . and remains a sentinel in the array; traversal checks for that sentinel before visiting, so absent branches are skipped safely. Starting at A, preorder visits node-left-right, inorder visits left-node-right, and postorder visits left-right-node. The three traversals are appended to separate strings and printed on three lines, in that order.
Every node is visited once by each traversal. Since there are three traversals, the total running time is O(N) and the stored child links and output are O(N); the recursive call stack is O(H), where H is the tree height.
import java.io.*;
import java.util.*;
public class Main {
static char[][] children = new char[26][2];
static StringBuilder preorder = new StringBuilder();
static StringBuilder inorder = new StringBuilder();
static StringBuilder postorder = new StringBuilder();
static void traverse(int node) {
if (node < 0) return;
preorder.append((char) ('A' + node));
traverse(children[node][0] == '.' ? -1 : children[node][0] - 'A');
inorder.append((char) ('A' + node));
traverse(children[node][1] == '.' ? -1 : children[node][1] - 'A');
postorder.append((char) ('A' + node));
}
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(input.readLine().trim());
for (int i = 0; i < n; i++) {
StringTokenizer row = new StringTokenizer(input.readLine());
int node = row.nextToken().charAt(0) - 'A';
children[node][0] = row.nextToken().charAt(0);
children[node][1] = row.nextToken().charAt(0);
}
traverse('A' - 'A');
System.out.println(preorder);
System.out.println(inorder);
System.out.println(postorder);
}
}