interval tree solution merge intervals

class IntervalTree{
public:
    int middle;
    int start, end;
    IntervalTree *left, *right;
    IntervalTree(int s, int e): start(s), end(e), middle((s+e)/2){
        this->left=this->right=NULL;
    }
};

void InsertInterval(IntervalTree *node, Interval ¤tInterval){
    if(node == NULL)
        return;

    if(currentInterval.end<node->middle){
        if(node->left)
            return InsertInterval(node->left, currentInterval);
        else{
            IntervalTree *newnode = new IntervalTree(currentInterval.start, currentInterval.end);
            node->left = newnode;
            return;
        }
    }

    if(currentInterval.start>node->middle){
        if(node->right)
            return InsertInterval(node->right, currentInterval);
        else{
            IntervalTree *newnode = new IntervalTree(currentInterval.start, currentInterval.end);
            node->right = newnode;
            return;
        }
    }

    //insert it to current node
    node->start=min(node->start, currentInterval.start);
    node->end=max(node->end, currentInterval.end);
}

So, when you want to merge the intervals, you will do something like below:

void QueryInterval(vector<Interval> &retV, IntervalTree *node){
    //retV is the return vector
    vector<Interval> leftIntervals;
    vector<Interval> rightIntervals;

    bool mergeleft = false; //whether current node merge with any intervals from left child.
    if(node->left){
        //return the merge of all intervals in left child.
        QueryInterval(leftIntervals, node->left);
        //merge left interval with myself.
        MergeLeftInterval(leftIntervals, node, retV, mergeleft);
    }

    if(!mergeleft){ //if we did not merge left intervals, add a new one
        Interval newinterval;
        newinterval.start = node->start;
        newinterval.end = node->end;
        retV.push_back(newinterval);
    }

    if(node->right){
        QueryInterval(rightIntervals, node->right);
        MergeRightInterval(rightIntervals, node, retV);
    }

    return;
}

void MergeLeftInterval(vector<Interval> &leftIntervals, IntervalTree *node, vector<Interval> &retV, bool &merged){
    for(int i=0; i<leftIntervals.size(); i++){
        if(leftIntervals[i].end>=node->start){
            Interval newinterval;
            newinterval.start = min(leftIntervals[i].start, node->start);
            newinterval.end = node->end;
            retV.push_back(newinterval);
            merged = true;
            break;
        } else {
            retV.push_back(leftIntervals[i]);
        }
    }
}

void MergeRightInterval(vector<Interval> &rightIntervals, IntervalTree *node, vector<Interval> &retV){
    for(int i=0; i<rightIntervals.size(); i++){
        if(rightIntervals[i].start<=node->end){
            retV[retV.size()-1].end = max(rightIntervals[i].end, node->end);
        } else{
            retV.push_back(rightIntervals[i]);
        }
    }
}