Interval Tree

Difficulty Level Medium
Frequently asked in Amazon Google Intuit Oracle Qualtrics
TreeViews 3233

In the interval tree problem, we have given a set of intervals and three types of queries

  1. addInterval(x,y): Add an interval (x,y) to the set
  2. removeInterval(x,y): Remove an interval (x,y) from the set
  3. checkInterval(x,y): Check if interval (x,y) overlaps with some existing interval

Design a data structure( Interval Tree ) to perform the above mentioned 3 operations.

Example

Interval Tree

Input
Insert(5, 10)
Insert(3, 8)
Insert(10, 15)
Insert(16, 18)
Insert(9, 11)
Insert(1, 1)
CheckOverlap(1, 2)
CheckOverlap(7, 11)
CheckOverlap(20, 25)
Delete(1, 1)
Delete(10, 15)
CheckOverlap(12, 14)
CheckOverlap(8, 15)
CheckOverlap(1, 2)
Delete(5, 10)
Delete(1, 2)
Delete(8, 15)
Output
true
true
false
false
true
false

Algorithm for Interval Tree

The idea is to use an augmented self balancing Binary Tree. Every node stores the following information

  • An interval [l, r], where l is the starting point of the interval, and r is the ending point of the interval.
  • max, the maximum ending point in the left and right subtree rooted with this node.

Insertion and Deletion

The starting point (l) of the interval is used to maintain the order in self balancing Binary Search Tree.
Insert and Delete are operations are performed the same as general self-balancing Binary Search Tree.

Overlap Searching

Search if an interval I(x, y) overlaps with some interval in the self-balancing Binary Search Tree,

  1. Start from the root, if I(x, y) overlaps with root, return root.
  2. If the max value of the current node is greater than the starting point of I, search in the left subtree.
  3. Else search in the right subtree.

JAVA Code for Interval Tree

public class IntervalTree {
    // class representing the node of interval tree
    static class Node {
        int l;
        int r;
        int max;

        Node left, right;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            this.max = r;
        }
    }

    // Function to insert an interval in interval tree
    public static Node insert(Node root, int l, int r) {
        // Insert like normal BST, by considering root.l as the key element
        if (root == null) {
            return new Node(l, r);
        }

        if (l < root.l) {
            root.left = insert(root.left, l, r);
        } else if (l > root.l) {
            root.right = insert(root.right, l, r);
        } else {
            if (r < root.r) {
                root.left = insert(root.left, l, r);
            } else {
                root.right = insert(root.right, l, r);
            }
        }

        // If current node's max is less than r, then update max
        if (root.max < r) {
            root.max = r;
        }

        return root;
    }

    private static boolean checkOverlap(Node root, int l, int r) {
        // If current node is null, return false
        if (root == null) {
            return false;
        }

        // If overlaps return true
        if (root.l <= r && l <= root.r) {
            return true;
        }

        // If max value of current is greater than starting point of I(l)
        // search in left subtree
        if (root.left != null && root.left.max >= l) {
            return checkOverlap(root.left, l, r);
        }

        // Else search in right subtree
        return checkOverlap(root.right, l, r);
    }

    // Function to delete a binary tree, same as normal delete in a BST
    private static Node delete(Node root, int l, int r) {
        if (root == null) {
            return null;
        }

        if (l < root.l) {
            root.left = delete(root.left, l, r);
        } else if (l > root.l) {
            root.right = delete(root.right, l, r);
        } else {
            if (r < root.r) {
                root.left = delete(root.left, l, r);
            } else if (r > root.r) {
                root.right = delete(root.right, l, r);
            } else {
                if (root.left == null)
                    return root.right;
                else if (root.right == null)
                    return root.left;

                // Find the minimum value in the right subtree of root
                Node curr = root.right;
                while (curr.left != null) {
                    curr = curr.left;
                }
                root.l = curr.l;
                root.r = curr.r;

                root.right = delete(root.right, root.l, root.r);
            }
        }

        return root;
    }

    public static void main(String[] args) {
        Node root = null;
        root = insert(root, 5, 10);
        root = insert(root, 3, 8);
        root = insert(root, 10, 15);
        root = insert(root, 16, 18);
        root = insert(root, 9, 11);
        root = insert(root, 1, 1);

        System.out.println(checkOverlap(root, 1, 2));
        System.out.println(checkOverlap(root, 7, 11));
        System.out.println(checkOverlap(root, 20, 25));

        root = delete(root, 1, 1);
        root = delete(root,10, 15);

        System.out.println(checkOverlap(root, 12, 14));
        System.out.println(checkOverlap(root, 1, 2));
        System.out.println(checkOverlap(root, 8, 15));
    }
}
true
true
false
false
false
true

C++ Code for Interval Tree

#include <bits/stdc++.h>
using namespace std;

// class representing the node of interval tree
class Node {
    public:
    int l, r, max;
    Node* left;
    Node* right;
    Node(int lVal, int rVal) {
        l = lVal;
        r = rVal;
        max = rVal;
        left = right = NULL;
    }
};

// Function to create a new Node
Node* newNode(int l, int r) {
    Node* node = new Node(l, r);
    return node;
}

// Function to insert an interval in interval tree
Node* insert(Node* root, int l, int r) {
    if (root == NULL) {
        return newNode(l, r);
    }
    
    if (l < root->l) {
        root->left = insert(root->left, l , r);
    } else if (l > root->l) {
        root->right = insert(root->right, l, r);
    } else {
        if (r < root->r) {
            root->left = insert(root->left, l, r);
        } else {
            root->right = insert(root->right, l, r);
        }
    }
    
    // If current node's max is less than r, then update max
    if (root->max < r) {
        root->max = r;
    }
    
    return root;
}

bool checkOverlap(Node *root, int l, int r) {
    // If current node is null, return false
    if (root == NULL) {
        return false;
    }
    
    // If overlaps return true
    if (root->l <= r && l <= root->r) {
        return true;
    }
    
    // If max value of current is greater than starting point of I(l)
    // search in left subtree
    if (root->left != NULL && root->left->max >= l) {
        return checkOverlap(root->left, l, r);
    }
    
    // Else search in right subtree
    return checkOverlap(root->right, l, r);
}

// Function to delete a binary tree, same as normal delete in a BST
Node* deleteInterval(Node* root, int l, int r) {
    if (root == NULL) {
        return NULL;
    }
    
    if (l < root->l) {
        root->left = deleteInterval(root->left, l, r);
    } else if (l > root->l) {
        root->right = deleteInterval(root->right, l, r);
    } else {
        if (r < root->r) {
            root->left = deleteInterval(root->left, l, r);
        } else if (r > root->r) {
            root->right = deleteInterval(root->right, l, r);
        } else {
            // This is the interval to be deleted
            if (root->left == NULL)
                return root->right;
            else if (root->right == NULL)
                return root->left;
                
            // Find the minimum value in the right subtree of root
            Node* curr = root->right;
            while (curr->left != NULL) {
                curr = curr->left;
            }
            root->l = curr->l;
            root->r = curr->r;
            
            root->right = deleteInterval(root->right, root->l, root->r);
        }
    }
    
    return root;
}

int main() {
    Node *root = NULL;
    root = insert(root, 5, 10);
    root = insert(root, 3, 8);
    root = insert(root, 10, 15);
    root = insert(root, 16, 18);
    root = insert(root, 9, 11);
    root = insert(root, 1, 1);
    
    if (checkOverlap(root, 1, 2))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 7, 11))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
    if (checkOverlap(root, 20, 25))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    root = deleteInterval(root, 1, 1);
    root = deleteInterval(root,10, 15);
    
    if (checkOverlap(root, 12, 14))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 8, 15))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 1, 2))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    return 0;
}
true
true
false
false
true
false

Complexity Analysis for Interval Tree

For insertion and deletion:

Time Complexity= O(h), where h is the height of BST (Binary Search Tree) and for a balanced BST h is log(n).

For searching:

Time Complexity = O(h), where h is the height of BST(Binary Search Tree) and for a balanced BST h is log(n).

References

Translate »