Challenge: Values in a Range

Lab C++ Intermediate 20 points

Build a BST from n numbers, then read lo hi. Print all values with lo ≤ value ≤ hi in sorted order (or none), skipping subtrees that can't contain answers.

Input

Line 1: n. Line 2: n numbers. Line 3: lo hi.

Output

The values, or none.

Example

Input

7
50 30 70 20 40 60 80
35 65

Output

40 50 60

Sample input available Sample output available

Editor

C++

Hints

Only go left if node->value > lo.

Only go right if node->value < hi.

Solution explanation

Pruning means you only visit about height + answers nodes.

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 collect(Node* n, int lo, int hi, vector<int>& out) {
    if (!n) return;
    if (n->value > lo) collect(n->left, lo, hi, out);
    if (lo <= n->value && n->value <= hi) out.push_back(n->value);
    if (n->value < hi) collect(n->right, lo, hi, out);
}

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

Output

Answer