# C++ solution using an (unbalanced) custom BST, with heavy comments

• ``````/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class SummaryRanges {

/*
* Basic idea: The set of disjoint intervals at any point itself is an ordered set.
* Thinking of the intervals marked along the number line, it is easy to see that there is an ordering of intervals.
* Since they are disjoint, we could either order them by the start point (l) or the end point (r), and get the same result.
*
* Supports insertion in O( log I ) and getIntervals() in O(I) where I is the number of intervals.
*
* Instead of using std::set<>, we implement the requried BST operations from scratch.
*/

// Structure to hold a node in the BST. Each node in the BST is an interval, i.e. a pair [l, r] of numbers.
struct TreeNode {
int l, r; // [l, r] are the ends of the interval
TreeNode *left, *right, *parent;
TreeNode( TreeNode *parent_, int l_, int r_ ) : l ( l_ ), r( r_ ), left( nullptr ), right( nullptr ), parent( parent_ ) {}
} *m_root;

// The usual BST successor method
TreeNode *successor( TreeNode *node ) {
if( !node )
return nullptr;
if( !node->right ) {
while( node->parent && node == node->parent->right )
node = node->parent;
if( !node->parent )
return nullptr;
node = node->parent;
}
if( node->right ) {
node = node->right;
while( node->left )
node = node->left;
}
return node;
}

// The usual BST predecessor method
TreeNode *predecessor( TreeNode *node ) {
if( !node )
return nullptr;
if( !node->left ) {
while( node->parent && node == node->parent->left )
node = node->parent;
if( !node->parent )
return nullptr;
node = node->parent;
}
if( node->left ) {
node = node->left;
while( node->right )
node = node->right;
}
return node;
}

// This method takes two intervals on the tree, and if they can be coalesced, coalesces them.
// Assumes BST structure is preserved.
//
// Basically, a pair of intervals like [1, 3] and [4, 7] can be coalesced into [1, 7].
// This algorithm is similar to BST delete -- we delete one of the intervals and extend the other.
// Since these form a pair of subsequent nodes in an in-order traversal of the tree, at least one of the two given nodes has < 2 children

void coalesce( TreeNode *a, TreeNode *b ) {
if( !a || !b || a == b )
return;

if( ( b->r + 1 == a->l ) == ( a->r + 1 == b->l ) )
return;

// To avoid the complicated case of removing a node with both children, we pick the easier one (the one with one or zero children) to splice out.
TreeNode *spliceOut = ( (a->left && a->right ) ? b : a );
TreeNode *other = (spliceOut == a ? b : a );
assert( ! ( spliceOut->left && spliceOut->right ) );

TreeNode *swapChild = nullptr;

// parentPatch is the pointer to the pointer in the parent of spliceOut that currently points to spliceOut.
// we shall later repoint the pointer to point to spliceOut's child, if any.
TreeNode **parentPatch = ( spliceOut->parent ?
&( spliceOut->parent->left == spliceOut ? spliceOut->parent->left : spliceOut->parent->right )
: nullptr
);

// Handle the case where spliceOut has a child : put the child in spliceOut's place
if( spliceOut->left || spliceOut->right ) {
swapChild = ( spliceOut->left ? spliceOut->left : spliceOut->right );
swapChild->parent = spliceOut->parent;
}
( parentPatch ? *parentPatch : m_root ) = swapChild; // swapChild could be nullptr

// Do the actual task of extending the intervals, completing the coalesce operation.
if( other->l == spliceOut->r + 1 )
other->l = spliceOut->l;
else
other->r = spliceOut->r;

// Free the spliced out node
delete spliceOut;
}

public:
/** Initialize your data structure here. */
SummaryRanges() : m_root( nullptr ) {

}

// This method is similar to BST insert, but with some additional complications.
// We keep working down the tree looking for the right place to insert, just as in BST insert,
// making a decision to go left / right at each stage.
//
// However, one of four cases could occur when we have found the "right" place:
// 1. val was already added, in which case there is an interval [l, r] that contains val.
//      We have nothing to do in this case.
// 2. There is an interval [val + 1, r] in the tree
//      In this case, we extend the interval to [val, r],
//      and then see if the interval can now be coalesced with its predecessor
// 3. There is an interval [l, val - 1] in the tree
//      In this case, we extend the interval to [l, val],
//      and then see if the interval can now be coalesced with its successor
// 4. None of the above -- val was not found in the tree, and does not lie at an interval edge
//      In this case, we add the interval [val, val] to the tree at the appropriate location

if( !m_root ) {
m_root = new TreeNode( nullptr, val, val );
return;
}

TreeNode *curr = m_root, *parent = nullptr;
while( curr ) {
if( curr->l <= val && val <= curr->r ) {
// Case 1: already in our tree, nothing to do
return;
}
if( curr->l == val + 1 ) {
// Case 2: coalesce left
curr->l = val; // expand the interval to the left
TreeNode *pred = predecessor( curr );
coalesce( pred, curr );
return;
}
if( curr->r == val - 1 ) {
// Case 3: coalesce right
curr->r = val; // expand to the right
TreeNode *succ = successor( curr );
coalesce( succ, curr );
return;
}

// We haven't yet found our insert point, look around
parent = curr;
if( curr->r < val )
curr = curr->right;
else
curr = curr->left;
}

// Case 4: val was not found. Insert the new interval [val, val] under the appropriate insertion point.
( parent->r < val ? parent->right : parent->left ) = new TreeNode( parent, val, val );

}

// This method is a straightforward in-order traversal. I like to use a recursive form to do the in-order traversal,
// contained in a lambda function object. The function object captures the result vector and writes to it as a side-effect.
vector<Interval> getIntervals() {
std::vector<Interval> v;
std::function<void( const TreeNode * )> inOrder = [&v, &inOrder]( const TreeNode *node ) {
if( !node )
return;
inOrder( node->left );
v.emplace_back( node->l, node->r );
inOrder( node->right );
};
inOrder( m_root );
return v;
}
};

/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();