RebuildBST.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Node{
public:
    int val;
    Node *left;
    Node *right;
    Node(int v): val(v){
        left = NULL;
        right = NULL;
    }
};

Node* convert(vector<int> &vec, int start, int end);
void preOrderTraverse(Node* root);
void inOrderTraverse(Node* root);
Node* convert2(vector<int>&vec, int rightParent);
Node* newConvert(vector<int>&vec);

int main(){
    int arr[] ={10, 7, 5, 9, 8, 15, 12};
    //int arr[] = {14, 11, 7, 2, 1, 4, 3, 5, 6, 8, 10, 9, 12, 13, 15};
    //int arr[] = {10, 11, 12, 13, 14};
    //int arr[] = {14, 7, 5, 9, 8, 10, 11, 13, 12, 19, 15, 16, 18, 17, 20};
    int len = sizeof(arr) / sizeof(int);
    vector<int> vec1(&arr[0], &arr[len]);
    Node* res1 = convert(vec1, 0, len - 1);  // O(N^2)
    vector<int> vec2(&arr[0], &arr[len]);    // O(N)
    Node* res2 = newConvert(vec2);
    cout << "Preorder traverse of BST generated by two methods: " << endl;
    preOrderTraverse(res1);
    cout << endl;
    preOrderTraverse(res2);
    cout << endl << endl;
    cout << "Inorder traverse of BST generated by two methods:" << endl;
    inOrderTraverse(res1);
    cout << endl;
    inOrderTraverse(res2);
    cout << endl << endl;
    return 0;
}

Node* convert(vector<int> &vec, int start, int end){ // O(N^2)
    if(start > end) return NULL;
    int rootVal = vec[start];
    Node* root = new Node(rootVal);
    int index = end + 1;
    for(int i = start + 1; i <= end; ++i){
        if(vec[i] > rootVal){
            index = i;
            break;
        }
    }
    root->left = convert(vec, start + 1, index - 1);
    root->right = convert(vec, index, end);
    return root;
}

Node* newConvert(vector<int>& vec){
    int rootVal = vec[0];
    Node* root = new Node(rootVal);
    vec.erase(vec.begin());
    int curMax = rootVal;
    if(rootVal > vec[0]){
        root -> left = convert2(vec, rootVal);   // call convert2 method
    }
    if(rootVal < vec[0]){
        root -> right = convert2(vec, INT_MAX);  // call convert2 method, use INT_MAX there is no right parent
    }
    return root;
}

Node* convert2(vector<int> &vec, int rightParent){  // O(N)
    if(vec.size() == 0) return NULL;
    int rootVal = vec[0];
    Node* root = new Node(rootVal);
    vec.erase(vec.begin());                       // erase the first element
    if(vec[0] < rootVal){
        root -> left = convert2(vec, rootVal);
    }
    if(rootVal < vec[0] && vec[0] < rightParent){   // compare with right parent value  
        root -> right = convert2(vec, rightParent);
    }
    return root;
}

void preOrderTraverse(Node* root){
    if(root == NULL) return;
    cout << root->val << ", ";
    preOrderTraverse(root->left);
    preOrderTraverse(root->right);
}

void inOrderTraverse(Node* root){
    if(root == NULL) return;
    inOrderTraverse(root->left);
    cout << root->val << ", ";
    inOrderTraverse(root->right);
}