Share my BST interval tree solution C++ No sorting!


  • 6
    H

    I share this solution because my friend was asked in his FB interview. He was asked to do it without sorting, for a large stream of intervals. The solution can be interval tree, but that is too complicated. Here I maintain a BST of distinct intervals. We dont need to maintain all the intervals like interval tree. We will merge intervals while we inserting. The code did not balance the tree. That is why performance is still 500+ms.

    Suppose we already have a BST of disjoint intervals. Given a new interval A, it will first find the toppest interval that has overlapping with A. Suppose it is B. Until now everything is easy. We simply traversed tree to reach this.

    Then, it will try to expand interval B. Now it becomes tricky. There are 3 cases. 1 case is simple. For the other 2 cases, you will need to delete currentNode, because it is already merged. You need to always correctly maintain prevNode and direction, in order to merge correctly in next round. For 1 case, you can end there. For another case, you need to continue exploration.
    The 2nd and 3rd case have duplicate code. However, I just keep it for better understanding.

    The whole reason we can do this, is because: we will never meet a situation that we delete 1 node with 2 children but still keep its 2 children. If we remove 1 node, that means either his left or right is deleted. So, this is not really traditional node deletion in BST!!!!!!

    I only share my code that insert a new interval to a BST. Other parts are simple.
    Please see notes when we exploring left Children, comments are omitted when exploring right children.

    void InsertInterval(BSTInterval *node, Interval ¤tInterval, BSTInterval *prev, int sign){
    //sign=1 if prev->left = node, sign=-1 if prev->right=node. 
    
    int start=currentInterval.start, end = currentInterval.end;
    if(node==NULL){
        BSTInterval *newnode = new BSTInterval(start, end);
        if(sign==1){
            prev->left = newnode;
            return;
        }
        else{
            prev->right = newnode;
            return;
        }
    }
    if (node->start<=start && node->end>=end)
        return;
        
    if (node->start>end){
        InsertInterval(node->left, currentInterval, node, 1);
        return;
    }
    if (node->end<start){
        InsertInterval(node->right, currentInterval, node, -1);
        return;
    }
    
    
    /* Now we find the node that overlap with the interval we want to insert. 
       We start from here and merge intervals. */
    //newLeft is always the new start after explore. 
    int newLeft=min(start, node->start);
    if(start<node->start){
        BSTInterval * currentNode = node;
        BSTInterval * prevNode = NULL;
        while(currentNode != NULL){
            if (newLeft>currentNode->end){
                //apparently need to explore right direction. 
                prevNode = currentNode;
                currentNode = currentNode->right;
                sign = -1;
            }
            else if (newLeft>currentNode->start){
                //apparently currentNode is not node, otherwise will not hit here
                //so, it is safe to delete currentNode
                //also, in this case, no need to explore more nodes, why?
                newLeft=currentNode->start;
                clear(currentNode->right);
                currentNode->right=NULL;
                if(sign==1) 
                    prevNode->left = currentNode->left;
                else
                    prevNode->right = currentNode->left;
                //we don't need to explore. 
                delete currentNode;
                break;//no need to continue, why?
            }
            else{ 
                //be careful: currentNode will be deleted if it is not node
                //then, we need to update prevNode and sign directly
                //otherwise we can not properly delete next node!!!
                //this case still needs exploration.
                BSTInterval *leftChild = currentNode->left;
                if(currentNode!=node){
                    //prevNode and sign not changed. Just delete currentNode
                    clear(currentNode->right);
                    currentNode->right=NULL;
                    if(sign==1)
                        prevNode->left = leftChild;
                    else
                        prevNode->right = leftChild;
                    delete currentNode;
                }
                else{
                    //prevNode and sign changed. 
                    prevNode = currentNode;
                    sign = 1;
                }
                currentNode=leftChild;
            }
        }
    }
    node->start = newLeft;
    
    int newRight=max(end, node->end);
    if(end>node->end){
        BSTInterval * currentNode = node;
        BSTInterval * prevNode = NULL;
        while(currentNode != NULL){
            if (newRight<currentNode->start){
                prevNode = currentNode;
                currentNode = currentNode->left;
                sign = +1;
            }
            else if (newRight<currentNode->end){
                newRight=currentNode->end;
                clear(currentNode->left);
                currentNode->left=NULL;
                if(sign==1) 
                    prevNode->left = currentNode->right;
                else
                    prevNode->right = currentNode->right;
                delete currentNode;
                break;
            }
            else{ 
                BSTInterval *rightChild = currentNode->right;
                if(currentNode!=node){
                    clear(currentNode->left);
                    currentNode->left=NULL;
                    if(sign==1)
                        prevNode->left = rightChild;
                    else
                        prevNode->right = rightChild;
                    delete currentNode;
                }
                else{
                    prevNode = currentNode;
                    sign = -1;
                }
                currentNode=rightChild;                    
            }
        }
    }
    node->end = newRight;
    
    return;
    

    }


  • 0
    D

    this deserves more upvote since it's pretty innovative. thanks for sharing!


  • 0
    H

    Actually Interval tree is a better solution. BST interval tree is tedious, because as you see in the comments the node merge is tedious. If we turn to interval tree, the only question is how to retrieve the final result? That means we merge intervals later.


  • 0
    H

    I pasted new code here:
    https://leetcode.com/discuss/89328/share-my-interval-tree-solution

    It is using interval tree, it is easier to understand than BST intervals. The running time is almost the same.


  • 0
    H

    Basically, if you want to keep each BST node maintain one interval and keep each interval disjoint, it is not easy. Using interval trees, each node is still an interval, but 2 nodes can overlap. The insertion is then much easier. We defer the merging work when we need the final result.


Log in to reply
 

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