Challenge: Three Walks

Lab Java Beginner 10 points

Read a binary tree and print its preorder, inorder and postorder traversals, one per line, values separated by spaces.

Input

Line 1: n, the number of nodes (numbered 0 to n − 1; node 0 is the root). Then n lines, one per node in order: value left right, where left and right are child node numbers, or -1 for no child.

Output

Three lines: preorder, inorder, postorder.

Example

Input

Output

8 3 1 6 10 14
1 3 6 8 10 14
1 6 3 14 10 8

Sample input available Sample output available

Editor

Java

Hints

Write three small recursive methods – they differ only in where the node is added.

Or do all three in one walk: add to pre before the left call, to in between, to post after.

Solution explanation

All three are O(n): each node is visited once.

Show solution

import java.util.Scanner;

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class Main {
    static TreeNode[] build(Scanner sc) {
        int n = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n];
        int[] left = new int[n], right = new int[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new TreeNode(sc.nextInt());
            left[i] = sc.nextInt();
            right[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            if (left[i] != -1) nodes[i].left = nodes[left[i]];
            if (right[i] != -1) nodes[i].right = nodes[right[i]];
        }
        return nodes;
    }

    static void walk(TreeNode n, StringBuilder pre, StringBuilder in, StringBuilder post) {
        if (n == null) return;
        pre.append(n.value).append(' ');
        walk(n.left, pre, in, post);
        in.append(n.value).append(' ');
        walk(n.right, pre, in, post);
        post.append(n.value).append(' ');
    }

    public static void main(String[] args) {
        TreeNode root = build(new Scanner(System.in))[0];
        StringBuilder pre = new StringBuilder(), in = new StringBuilder(), post = new StringBuilder();
        walk(root, pre, in, post);
        System.out.println(pre.toString().trim());
        System.out.println(in.toString().trim());
        System.out.println(post.toString().trim());
    }
}

Output

Answer