Challenge: Sort With a BST

Lab Java Beginner 10 points

Insert n numbers into your own binary search tree (ignore duplicates), then print an inorder traversal – the different numbers in sorted order.

Input

Line 1: n. Line 2: n whole numbers.

Output

The different numbers in ascending order.

Example

Input

7
50 30 70 20 40 60 80

Output

20 30 40 50 60 70 80

Sample input available Sample output available

Editor

Java

Hints

insert: null → new node; smaller → go left; bigger → go right; equal → do nothing.

Inorder (left, node, right) prints a BST in sorted order.

Solution explanation

This is “tree sort”: O(n log n) when the tree stays bushy, O(n²) if the input is already sorted.

Show solution

import java.util.Scanner;

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

public class Main {
    static Node insert(Node node, int v) {
        if (node == null) return new Node(v);
        if (v < node.value) node.left = insert(node.left, v);
        else if (v > node.value) node.right = insert(node.right, v);
        return node;                       // duplicates are ignored
    }

    static void inorder(Node node, StringBuilder out) {
        if (node == null) return;
        inorder(node.left, out);
        if (out.length() > 0) out.append(' ');
        out.append(node.value);
        inorder(node.right, out);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node root = null;
        for (int i = 0; i < n; i++) root = insert(root, sc.nextInt());
        StringBuilder sb = new StringBuilder();
        inorder(root, sb);
        System.out.println(sb);
    }
}

Output

Answer