Challenge: Is It in the Tree?

Lab C++ Beginner 10 points

Build a BST from n numbers. For each of q queries print found or missing and how many nodes were checked.

Input

Line 1: n. Line 2: n numbers. Line 3: q. Line 4: q numbers.

Output

One line per query: found <steps> or missing <steps>.

Example

Input

6
8 3 10 1 6 14
4
6 7 8 15

Output

found 3
missing 3
found 1
missing 3

Sample input available Sample output available

Editor

C++

Hints

Count one step per node you look at.

Smaller: go left. Bigger: go right. nullptr: missing.

Solution explanation

Steps ≤ height of the 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;
}

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 q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        Node* cur = root;
        int steps = 0;
        while (cur) {
            steps++;
            if (t == cur->value) break;
            cur = t < cur->value ? cur->left : cur->right;
        }
        cout << (cur ? "found " : "missing ") << steps << endl;
    }
    return 0;
}

Output

Answer