# Share some idea using customized BST, 152ms, C++

• This solution is not a pretty one: the code is long and somehow takes time to read, since I define my own BST tree, and there are some basic operation mixture with algorithm itself. But I still want to share for kind of way to solve this interesting problem.

There are lots of comments in the code, I hope you can understand by the comments. The basic idea for this algorithm is: build and maintain a BST with internal as node value, each time when add interval, do at most twice merge with exists nodes by following BST property; after merge, keep BST property the same.

The complexity of this algorithm is:

• getIntervals: O(# of intervals in tree)
``````class SummaryRanges {
public:
struct RangeTreeNode {
Interval range;
RangeTreeNode* left;
RangeTreeNode* right;
RangeTreeNode(Interval _val) : range(_val), left(nullptr), right(nullptr) {}
RangeTreeNode() : left(nullptr), right(nullptr) {}
};

SummaryRanges() {
Interval root_val(INT_MAX, INT_MIN);
root.range =  root_val;
}

/*
* two things should be noticed:
*   1) everytime, at most two Intervals could be merge, so at most two times of merge may happen.
*   2) based on 1), every time after merge happen, the BST properity should always be kept.
*/
// check if val already in some range in the tree, if so, current addNum is dup, ignore
if(isInRange(val, root.left)) return ;

// find if there exists some node that could do merge, if so, cur should return the lowest such node
RangeTreeNode* parent = &root, *cur = root.left;
while(cur != nullptr && cur->range.start-1 != val && cur->range.end+1 != val) {
parent = cur;
cur = (val < cur->range.start ? cur->left : cur->right);
}

// determine if such node exists or not, if not, then just simply insert the node into the tree
if(cur == nullptr) {
Interval ninterval(val, val);
RangeTreeNode* nnode = new RangeTreeNode(ninterval);
parent->left = (val < parent->range.start ? nnode : parent->left);
parent->right = (val > parent->range.end ? nnode : parent->right);
}else {
// otherwise, we have such node, do merge TWICE: first is val with cur node, another one is with the successor or prvior
// notice: in first merge, it is possible merge with left bound or right bound, so, depends on which side, different code handles
//
if(cur->range.start-1 == val) {
// merege with left bound of current node, in this case,
// we should find the previor and check if we can merge or not

/* following statement do first merge: */
cur->range.start = val;

/* following code do second merge: */
// also, second time merge should help with keeping BST properity
// the prvior, if exists, must occured in subtree, rooted with cur->left, the right most node
RangeTreeNode* rcur = cur->left, *rparent = cur->left;
for(;rcur != nullptr && rcur->right != nullptr; rparent = rcur, rcur = rcur->right) {}

// find this right most node, here, we have two case: first one is cur->right is nullptr(consider a tree with just root node, then merge)
// another one is not nullptr, we need to take care of second case.
if(rcur != nullptr && rcur->range.end+1 == val) {
// do second time merge
cur->range.start = rcur->range.start;
/* NOTICE: do not make any assumption about node rcur:
* there exists a case that this rcur node doesn't have right child(this makes rcur node is right most node)
* but this node may have left child, so when deal with second merge, the binary search tree properity should be kept,
* therefore, adjust the left subtree of node rcur. if here use nullptr instead, bug occurs, some node will miss, BST is not correct
*/
rparent->right = rcur->left;

// there also exists a case that rcur == cur->left,
// in this case, this node just has left child and no right child
if(rparent == rcur) {
cur->left = rcur->left;
}
// after merge, the rcur node is no longer useful, delete it.
// afterall, the node is abandoned, except for pointer rcur point to this node,
// no other pointer points to it, whether like or not, this node bust be deleted
delete rcur;
}
}else {
// similar with left bound merge, this statements take care of right bound
cur->range.end = val;
RangeTreeNode* lcur = cur->right, *lparent = cur->right;
for(;lcur != nullptr && lcur->left != nullptr; lparent = lcur, lcur = lcur->left) {}
if(lcur != nullptr && lcur->range.start-1 == val) {
cur->range.end = lcur->range.end;
lparent->left = lcur->right;
if(lparent == lcur) {
cur->right = lcur->right;
}
delete lcur;
}
}
}
return ;
}

vector<Interval> getIntervals() {
vector<Interval> ans;
getIntervals(ans, root.left);
return ans;
}

~SummaryRanges() {
del_tree(root.left);
}

private:
// dummy root node, make life easier
RangeTreeNode root;

void getIntervals(vector<Interval> &ans, RangeTreeNode* rt) {
if(rt == nullptr) return ;
getIntervals(ans, rt->left);
ans.push_back(rt->range);
getIntervals(ans, rt->right);
}

bool isInRange(int val, RangeTreeNode* rt) {
if(rt == nullptr) return false;
return (val>=rt->range.start && val<=rt->range.end) || isInRange(val, rt->left) || isInRange(val, rt->right);
}

void del_tree(RangeTreeNode* rt) {
if(rt == nullptr) return ;
del_tree(rt->left);
del_tree(rt->right);
delete rt;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.