@yubad2000 Right, I knew that. But apparently I failed to follow that again. But I figured out the fix for it: I have to return the root to the next call, and construct new node as left or right subtree for root, but have to return root for next call. Here's my updated code, it passed 8/9 test cases:

public class SummaryRanges {
Node root;
/** Initialize your data structure here. */
public SummaryRanges() {
root = null;//new Node(Integer.MIN_VALUE, new Interval());
}
public void addNum(int val) {
root = addNum(val, root);
}
public Node addNum(int val, Node root) {
if(root == null || root.start == Integer.MIN_VALUE){
root = new Node(val, new Interval(val, val));
return root;
}
else if(root.shouldExpandAndUpdateInterval(val) == -1){
root.interval.start = val;
root.start = val;
//merge this root with its left subtree if necessary
return mergeWithLeft(root, root.left);
}
else if(root.shouldExpandAndUpdateInterval(val) == 1){
//this val should be inserted into the RIGHT subtree somewhere or create a new interval for it
root.interval.end = val;
//merge this root with its right subtree if necessary
return mergeWithRight(root, root.right);
}
else if(root.shouldExpandAndUpdateInterval(val) == 2){
root.right = addNum(val, root.right);
return root;
}
else if(root.shouldExpandAndUpdateInterval(val) == -2){
root.left = addNum(val, root.left);
return root;
}
return root;
}
private Node mergeWithRight(Node mergedRoot, Node rightNode) {
if(rightNode == null) return mergedRoot;
//check this rightNode first before checking its left subtree
if(rightNode.start == mergedRoot.interval.end || rightNode.start -1 == mergedRoot.interval.end){
//expand this mergedRoot.interval.end
mergedRoot.interval.end = rightNode.interval.end;
Node left = rightNode.left;
Node right = rightNode.right;
if(left != null){
left.right = right;
} else {
left = right;
}
mergedRoot.right = left;
}
if(rightNode.left != null && rightNode.left.left == null) {
//this is the node that should be merged if possible since it has the smallest start point
if(rightNode.left.start == mergedRoot.interval.end || rightNode.left.start - 1 == mergedRoot.interval.end){
mergedRoot.interval.end = rightNode.left.interval.end;
Node right = rightNode.left.right;
rightNode.left = right;
}
}
if(rightNode.left != null){
return mergeWithRight(mergedRoot, rightNode.left);
}
return mergedRoot;
}
private Node mergeWithLeft(Node mergedRoot, Node leftNode) {
if(leftNode == null) return mergedRoot;
//check this leftNode itself first before checking its right subtree
if(leftNode.interval.end == mergedRoot.start || leftNode.interval.end + 1 == mergedRoot.start){
mergedRoot.start = leftNode.interval.start;
mergedRoot.interval.start = leftNode.interval.start;
Node left = leftNode.left;
Node right = leftNode.right;
if(left != null){
left.right = right;
} else {
left = right;
}
mergedRoot.left = left;
}
if(leftNode.right != null && leftNode.right.right == null){
//this is the node that should be merged with mergedRoot if possible since it has the largest end
if(leftNode.right.interval.end == mergedRoot.start || leftNode.right.interval.end + 1 == mergedRoot.start){
mergedRoot.start = leftNode.right.interval.start;
mergedRoot.interval.start = leftNode.right.interval.start;
Node left = leftNode.right.left;
leftNode.right = left;
}
}
if(leftNode.right != null){
return mergeWithLeft(mergedRoot, leftNode.right);
}
return mergedRoot;
}
public List<Interval> getIntervals() {
List<Interval> result = new ArrayList<Interval>();
dfs(root, result);
return result;
}
private void dfs(Node root, List<Interval> result) {
if(root == null) return;
if(root.left != null) dfs(root.left, result);
result.add(root.interval);
if(root.right != null) dfs(root.right, result);
}

}

class Node{

Node left;

Node right;

Interval interval;

int start;

public Node(int start){
this.start = start;
}
public Node(int start, Interval interval){
this.start = start;
this.interval = interval;
}
public Node(Interval interval){
this.interval = interval;
}
public int shouldExpandAndUpdateInterval(int otherVal){
//1 means otherVal is greater than interval.end by 1 and current interval should be expanded by 1
//-1 means otherVal is smaller than interval.start by 1 and current interval should be expanded by 1
//0 means otherVal lies in between the current interval
if(interval.end + 1 == otherVal) return 1;
if(otherVal + 1 == start) return -1;
else if(otherVal <= interval.end && otherVal >= interval.start) return 0;
else if(otherVal - interval.end > 1) return 2;//this means it should continue with the RIGHT subtree
else return -2;//this means it should continue with the LEFT subtree
}
}

The last test case is an extreme test case, too long to be pasted here, and from my eyes, I could hardly spot the difference between my output and the expected output.

So I guess the hope to get this code AC'ed is to find the bug in the code?!?

I'm really impressed by Leetcode's test coverage, :) but I don't know where my code is making it unhappy. :(