Find Structures of Trees [NCTU Floor 7]

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

int preIndex;

class node{
    public:
        char data;
        node* left;
        node* right;
};

node* newNode(char data){
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;

    return (Node);
}

int search(string arr, int strt, int end, char value){
    int i;
    for(i = strt; i <= end; i++)
        if(arr[i] == value)
            return i;
    return 0;
}

node* buildTree(string in, string pre, int start, int end){
    if(start > end)
        return NULL;
    node* root = newNode(pre[preIndex++]);
    if(start == end)
        return root;
    int i;
    for(i = start; i <= end; i++)
        if(root->data == in[i])
            break;

    if(start <= end){
        root->left = buildTree(in, pre, start, i - 1);

        root->right = buildTree(in, pre, i + 1, end);
    }

    return root;
}

void printInorder(node* node, string& ans){
    if(node == NULL)
        return;
    printInorder(node->left, ans);
    printInorder(node->right, ans);
    ans += node->data;
}

void deleteTree(node*& node){
    if(node == NULL) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

int main(){
    string input;

    while(getline(cin, input)){
        preIndex = 0;
        stringstream ss(input);
        string in, pre;
        ss >> pre >> in;
        string ans = "";
        int len = in.size();
        node* root = buildTree(in, pre, 0, len - 1);
        printInorder(root, ans);
        deleteTree(root);
        cout << ans << endl;
    }
    return 0;
}