SMMR-083: Binary Search Tree

#include <bits/stdc++.h>

using namespace std;

typedef struct node{
    int data;
    node *left, *right;
};

node *create(int data){
    node *Node = new node;
    Node -> data = data;
    Node -> left = nullptr;
    Node -> right = nullptr;
    return Node;
}

node *insert(node *root, int data){
    if(root == nullptr)
        return create(data);
    if(data < root -> data)
        root -> left = insert(root -> left, data);
    else
        root -> right = insert(root -> right, data);
    return root;
}

vector <int> ans;

bool find(node *root, int data){
    if(root == nullptr)
        return false;
    ans.push_back(root -> data);
    if(data < root -> data)
        return find(root -> left, data);
    else if(data > root -> data)
        return find(root -> right, data);
    find(root -> right, data);
    return true;
}

int main(){

    int n;
    scanf("%d", &n);

    node *root = nullptr;

    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d", &x);
        root = insert(root, x);
    }

    int m;
    scanf("%d", &m);

    for(int i=1;i<=m;i++){
        int x;
        scanf("%d", &x);
        bool fnd = find(root, x);
        int sz = ans.size();
        int idx = sz-1;
        for(int i=sz-1;i>=0;i--){
            if(ans[i] == x){
                idx = i;
                break;
            }
        }
        for(int i=0;i<=idx;i++) printf("%d ", ans[i]);
        if(!fnd) printf("0");
        printf("\n");
        if(!ans.empty()) ans.clear();
    }

    return 0;
}