SMMR-T083: Binary Search Tree

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

typedef struct node{
    int data;
    node *left;
    node *right;
    node(int item){
        data = item;
        left = NULL;
        right = NULL;
    }
    node(int item, node *r, node *l){
        data = item;
        left = l;
        right = r;
    }
}node;

vector<int> tmp;
vector<int> ans;
int nn, ql;
bool found;
node *root;

void PrintPreorder(node *root){
    if(root == NULL){
        return;
    } else {
        cout << root -> data << " ";
        PrintPreorder(root -> left);
        PrintPreorder(root -> right);
        return;
    }
}

node *InsertNode(node *root, int data){
    if(root == NULL){
        return new node(data);
    } else {
        node *curr = root;
        node *prev;
        while(curr != NULL){
            prev = curr;
            if(data < curr -> data){
                curr = curr -> left;
            } else {
                curr = curr -> right;
            }
        }
        if(data < prev -> data){
            prev -> left = new node(data);
        } else {
            prev -> right = new node(data);
        }
        return root;
    }
}

void FindNode(node *root, int tr){
    if(tr == root -> data){
        tmp.push_back(root -> data);
        ans = tmp;
        found = true;
        if(root -> right != NULL){
            FindNode(root -> right, tr);
        }
        return;
    } else if(tr < root -> data){
        tmp.push_back(root -> data);
        if(root -> left != NULL){
            FindNode(root -> left, tr);
        } else {
            tmp.push_back(0);
            if(!found){
                ans = tmp;
            }
        }
        return;
    } else {
        tmp.push_back(root -> data);
        if(root -> right != NULL){
            FindNode(root -> right, tr);
        } else {
            tmp.push_back(0);
            if(!found){
                ans = tmp;
            }
        }
        return;
    }
}

int main(){

    int x;

    scanf("%d", &nn);
    for(int i = 0; i < nn; ++i){
        scanf("%d", &x);
        root = InsertNode(root, x);
    }
    scanf("%d", &ql);
    for(int i = 0; i < ql; ++i){
        scanf("%d", &x);
        tmp.clear();
        found = false;
        FindNode(root, x);
        for(auto x : ans){
            cout << x << " ";
        }
        cout << "\n";
    }

    return 0;
}