Build a BST and print its traversals

Problem

Read integer keys, insert them one by one (in input order) into an initially empty binary search tree, and print the tree's size, its four traversals and its height.

Duplicates: a key that is already in the tree is ignored (the tree is a set).

Input. The first line holds n (n ≥ 0), the number of keys; then n integers follow.

Output. Exactly these six lines, each traversal's keys separated by single spaces:

Size: <number of distinct keys>
In-order: <keys>
Pre-order: <keys>
Post-order: <keys>
Level-order: <keys>
Height: <height in edges>

For an empty tree each traversal line shows (empty) (e.g. In-order: (empty)) and the height is -1. A single node has height 0.

Example.

Input:
6
5 3 5 8 3 1

Output:
Size: 4
In-order: 1 3 5 8
Pre-order: 5 3 1 8
Post-order: 1 3 8 5
Level-order: 5 3 8 1
Height: 2

Your solution

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

class BST {
    private static class Node {
        int key;
        Node left, right;
        Node(int key) { this.key = key; }
    }

private Node root;
    private int size;

int size() { return size; }

void insert(int key) { root = insert(root, key); }

private Node insert(Node n, int key) {
        // TODO: recursive insert, ignoring duplicates; count new nodes in size
        return n;
    }

int height() { return height(root); }

private int height(Node n) {
        // TODO: -1 for an empty tree
        return -1;
    }

// TODO: inOrder(), preOrder(), postOrder(), levelOrder() returning the text
    //       after the label, e.g. " 1 3 5 8" or " (empty)"
}

public class BSTTraversals {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        BST tree = new BST();
        for (int i = 0; i < n; i++) tree.insert(in.nextInt());
        // TODO: print the six lines
    }
}

← D11.2 Top-k and the k-th largest value D12.2 Deleting keys from a BST →