# Java simple and easy understand solution based on naive BST

• use only BST. the key point is to merge the interval like [1,1] [3,3] if 2 was added. My solution is to find the rightmost or the leftmost in the sub tree to merge.

class Tree {
Interval interval;
Tree left;
Tree right;

Tree(int num) {interval = new Interval(num,num);}
}

public class SummaryRanges {

/** Initialize your data structure here. */
Tree root;
public SummaryRanges() {

}

public void addNum(int val) {
if(root == null) root = new Tree(val);
}

public void add(Tree now,int val){
if(now.interval.start <= val && val <= now.interval.end) return;
else if(now.interval.start == val+1){
now.interval.start = val;
Tree parent = now;
Tree find = now.left;
while(find != null && find.right != null) {parent = find;find = find.right;}
if(find != null && (find.interval.end == now.interval.start || find.interval.end+1 == now.interval.start)){
now.interval.start = find.interval.start;
if(parent == now) parent.left = find.left;
else parent.right = find.left;
}
}
else if(now.interval.end + 1 == val){
now.interval.end = val;
Tree parent = now;
Tree find = now.right;
while(find != null && find.left != null){parent = find;find = find.left;}
if(find != null &&  (find.interval.start == now.interval.end || find.interval.start-1 == now.interval.end)){
now.interval.end = find.interval.end;
if(parent == now) parent.right = find.right;
else parent.left = find.right;
}
}
else if(now.interval.start > val){
if(now.left == null) now.left = new Tree(val);
}
else{
if(now.right == null) now.right = new Tree(val);
}
}

public List<Interval> getIntervals() {
List ret = new ArrayList();
inOrder(root,ret);
return ret;
}

public void inOrder(Tree now, List ret){
if(now != null){
inOrder(now.left,ret);