Challenge: Sort with a BST

Lab C++ Beginner 10 points

Insert n numbers into your own BST in the order given (ignore duplicates). Print the inorder traversal and the tree's height.

Input

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

Output

Line 1: inorder values. Line 2: Height: <h>

Example

Input

7
50 30 70 20 40 60 80

Output

20 30 40 50 60 70 80
Height: 3

Sample input available Sample output available

Editor

C++

Hints

insert: nullptr is the spot; go left if smaller, right if bigger.

Inorder of a BST is sorted.

Solution explanation

Sorted input (test 2) gives height 5 for 5 values – a line, not a bushy tree.

Show solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int value) {
    if (!root) return new Node(value);
    if (value < root->value) root->left = insert(root->left, value);
    else if (value > root->value) root->right = insert(root->right, value);
    return root;
}

void inorder(Node* n, vector<int>& out) {
    if (!n) return;
    inorder(n->left, out);
    out.push_back(n->value);
    inorder(n->right, out);
}

int height(Node* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }

int main() {
    int n;
    cin >> n;
    Node* root = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        root = insert(root, x);
    }
    vector<int> out;
    inorder(root, out);
    for (size_t i = 0; i < out.size(); i++) cout << out[i] << (i + 1 < out.size() ? " " : "\n");
    cout << "Height: " << height(root) << endl;
    return 0;
}

Output

Answer