Posted on by Kalkicode
Code Tree

Implement interval tree

The problem at hand is the implementation of an interval tree, a data structure that efficiently stores and handles intervals (ranges) on a number line. Interval trees are primarily used to perform range queries efficiently, such as finding overlapping intervals or intervals that contain a given point. They find applications in various fields including computational geometry, scheduling, and database systems.

Problem Statement

Given a set of intervals, the goal is to construct an interval tree that supports efficient insertion of intervals and interval search queries. A search query involves finding intervals that overlap with a given interval.

Description with Example

Imagine a scenario where you are managing appointments at a clinic. Each appointment is represented by a time interval, where the start time and end time are recorded. To efficiently manage these appointments, you can use an interval tree. Let's consider a few appointment intervals:

  • Appointment 1: 22:00 - 22:30
  • Appointment 2: 03:00 - 07:00
  • Appointment 3: 16:00 - 28:00
  • ... and so on.

The interval tree will help you manage these appointments effectively, allowing for quick insertion and retrieval of overlapping intervals.

Idea to Solve

For Example interval :

[
    [22, 46],
    [3, 7],
    [33, 52],
    [23, 45],
    [16, 28],
    [12, 38],
    [24, 35],
    [2, 26],
    [35, 46]
]
Interval Tree

The key idea in constructing an interval tree is to use a binary search tree (BST) where each node represents an interval. Additionally, each node stores the maximum endpoint value of all the intervals in its subtree. This "max" value is essential to efficiently find overlapping intervals during search operations.

Pseudocode

Structure IntervalNode:
    low
    high
    max
    left
    right

Structure IntervalTree:
    root

Function newNode(intervalInfo):
    Create a new node
    Set node's low, high, and max
    Set left and right as NULL
    Return the node

Function addNode(tree, intervalInfo):
    Create a new node using newNode(intervalInfo)
    If tree.root is NULL:
        Set tree.root as the new node
        Return
    Initialize auxiliary as tree.root
    While auxiliary is not NULL:
        Update auxiliary's max if new node's max is greater
        If new node's low is less than auxiliary's low:
            If auxiliary's left is NULL:
                Set auxiliary's left as the new node
                Return
            Else:
                Move to auxiliary's left
        Else:
            If auxiliary's right is NULL:
                Set auxiliary's right as the new node
                Return
            Else:
                Move to auxiliary's right

Function preorder(node):
    If node is not NULL:
        Print node's interval and max
        Recursively call preorder(node's left)
        Recursively call preorder(node's right)

Function overlapSearch(node, low, high):
    If node is NULL:
        Return NULL
    If node's interval overlaps with [low, high]:
        Return node
    If node's left is not NULL and node's left's max is greater than or equal to low:
        Recursively call overlapSearch on node's left
    Else:
        Recursively call overlapSearch on node's right

Main:
    Initialize an empty interval tree using newTree()
    Create a list of interval values
    For each interval in the list:
        Add the interval to the interval tree using addNode
    Print "Preorder" and call preorder(tree.root)
    Search for overlapping intervals using overlapSearch and print the result

Algorithm Explanation

The pseudocode provided explains the implementation of interval tree, including functions to create nodes, add nodes to the tree, perform a preorder traversal, and search for overlapping intervals.

Code Solution

// C Program 
// Construct interval tree
#include <stdio.h>
#include <stdlib.h>


struct IntervalNode
{
    // Interval keys
    int low;
    int high; 
    int max;
    struct IntervalNode *left, *right; 
};
struct IntervalTree
{
    struct IntervalNode * root;
};
// Create new tree
struct IntervalTree *newTree()
{
    // Create dynamic tree
    struct IntervalTree *tree = 
      (struct IntervalTree *) malloc(sizeof(struct IntervalTree));
    
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    //return new tree
    return tree;
}



// This is creates and returns the new Interval tree Node node
struct IntervalNode *getNode(int intervalInfo[])
{
    // Create dynamic node
    struct IntervalNode *node = 
           (struct IntervalNode *) malloc(sizeof(struct IntervalNode));
    if (node != NULL)
    {
        
        node->low   = intervalInfo[0];
        node->high  = intervalInfo[1];
        node->max   = intervalInfo[1];
        node->left  = NULL;
        node->right = NULL;
    }
    else
    {
        //This is indicates, segmentation fault or memory overflow problem
        printf("Memory Overflow\n");
    }
    return node;
}


// This is creates and returns the new Interval tree Node node
void addNode(struct IntervalTree *tree, int intervalInfo[])
{
    struct IntervalNode*node = getNode(intervalInfo);

    if(tree->root==NULL)
    {
        // First node
        tree->root = node;
        return;
    }

    struct IntervalNode*auxilary = tree->root;

    // Add a Interval node into tree
    while(auxilary!=NULL)
    {

      
        if(auxilary->max < node->max)
        {
            // Change ancestor with new max value
            auxilary->max = node->max;
        }

        if(node->low < auxilary->low)
        {

            if(auxilary->left==NULL)
            {
                // Add new node
                auxilary->left = node;
                return;
            }
            else
            {
                // Visit left subtree
                auxilary = auxilary->left;
            }
        }
        else
        {

            if(auxilary->right==NULL)
            {
                // Add new node
                auxilary->right = node;
                return;
            }
            else
            {
                // Visit right subtree
                auxilary = auxilary->right;
            }
        }
    }
}

// Display preorder of interval tree
void preorder(struct IntervalNode *node) 
{ 
    if (node != NULL) 
    {
        printf("\n Interval : (%d %d) , max %d", 
               node->low,node->high,node->max);

        // Visit left and right subtree using recursively
        preorder(node->left); 
        preorder(node->right); 
    }
} 
struct IntervalNode *overlapSearch(
        struct IntervalNode *node, int low, int high) 
{ 
 
    if (node == NULL) 
    {
        return NULL;
    } 
  
    
    if(node->low <= high && low <= node->high )
    {
        // When resultant node found
        return node;
    }
    if (node->left != NULL && node->left->max >= low) 
    {
        return overlapSearch(node->left, low, high); 
    }
    else
    {
        return overlapSearch(node->right, low, high); 
    }

} 
int main()
{

    struct IntervalTree*tree = newTree();

    // Given intervals
    // Note intervals pairs are sorted order
    int intervalValue[][2] = {
        {22, 46}, {3, 7} , {33, 52}, 
        {23, 45}, {16,28}, {12, 38},
        {24,35} , {2,26} , {35,46}
    }; 
    // Get number of nodes
    int n =  sizeof(intervalValue)/sizeof(intervalValue[0]);

    // Add tree element
    for (int i = 0; i < n; ++i)
    {
        addNode(tree,intervalValue[i]);
    }

    /*
                   Max = 52
                   (22, 46)
                  /      \
             (38)/        \ (52)
              (3, 7)      (33, 52) 
             /    \        /     \
        (26)/      \(38)  /(45)   \(46)
         (2,26)  (16,28)(23, 45) (35,46) 
                  /       \
             (38)/         \ (35)
             (12 38)     (24,35)
                  
      --------------------------------
        Construct Interval tree
      -------------------------------
        Preorder
        Interval : (22 46) , max 52
        Interval : (3 7) , max 38
        Interval : (2 26) , max 26
        Interval : (16 28) , max 38
        Interval : (12 38) , max 38
        Interval : (33 52) , max 52
        Interval : (23 45) , max 45
        Interval : (24 35) , max 35
        Interval : (35 46) , max 46
      -------------------------------
    */
    // Display tree elements

    printf("\n \n Preorder");
    preorder(tree->root);

    // Search interval
    int low = 10;
    int high = 21;
    struct IntervalNode *ans = overlapSearch(tree->root,low,high);

    if(ans!=NULL)
    {
        printf("\n Search Interval (%d,%d) at (%d,%d)",
               low,high,ans->low,ans->high);
    }
    else
    {
        printf("\n Search Interval (%d,%d) : None", low,high);
    }
    return 0;
}

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
/*
    Java Program
    Construct interval tree
*/
// Interval Tree node
class IntervalNode {
    // Interval keys
    public int low;
    public int high;
    // Max of child
    public int max;
    public IntervalNode left;
    public IntervalNode right;
    public IntervalNode(int[] intervalInfo)
    {
        this.low = intervalInfo[0];
        this.high = intervalInfo[1];
        this.max = intervalInfo[1];
        this.left = null;
        this.right = null;
    }
}
public class IntervalTree
{
    public IntervalNode root;
    public IntervalTree()
    {
        this.root = null;
    }
    // This is creates and returns the new Interval tree Node node
    public void addNode(int[] intervalInfo)
    {
        IntervalNode node = new IntervalNode(intervalInfo);
        if (this.root == null)
        {
            // First node
            this.root = node;
            return;
        }
        IntervalNode auxilary = this.root;
        // Add a Interval node into tree
        while (auxilary != null)
        {
            if (auxilary.max < node.max)
            {
                // Change ancestor with new max value
                auxilary.max = node.max;
            }
            if (node.low < auxilary.low)
            {
                if (auxilary.left == null)
                {
                    // Add new node
                    auxilary.left = node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    auxilary = auxilary.left;
                }
            }
            else
            {
                if (auxilary.right == null)
                {
                    // Add new node
                    auxilary.right = node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    auxilary = auxilary.right;
                }
            }
        }
    }
    // Display preorder of interval tree
    public void preorder(IntervalNode node)
    {
        if (node != null)
        {
            System.out.print("\n Interval : (" + 
                    node.low + " " + node.high + ") , max " + node.max);
            // Visit left and right subtree using recursively
            preorder(node.left);
            preorder(node.right);
        }
    }
    public IntervalNode overlapSearch(IntervalNode node, int low, int high)
    {
        if (node == null)
        {
            return null;
        }
        if (node.low <= high && low <= node.high)
        {
            // When resultant node found
            return node;
        }
        if (node.left != null && node.left.max >= low)
        {
            return overlapSearch(node.left, low, high);
        }
        else
        {
            return overlapSearch(node.right, low, high);
        }
    }
    public static void main(String[] args)
    {
        IntervalTree tree = new IntervalTree();
        // Given intervals
        // Note intervals pairs are sorted order
        int[][] intervalValue = {
            {
                22 , 46
            },{
                3 , 7
            },{
                33 , 52
            },{
                23 , 45
            },{
                16 , 28
            },{
                12 , 38
            },{
                24 , 35
            },{
                2 , 26
            },{
                35 , 46
            }
        };
        // Get number of nodes
        int n = intervalValue.length;
        // Add tree element
        for (int i = 0; i < n; ++i)
        {
            tree.addNode(intervalValue[i]);
        }
        /*
                     Max = 52
                     (22, 46)
                    /      \
               (38)/        \ (52)
                (3, 7)      (33, 52) 
               /    \        /     \
          (26)/      \(38)  /(45)   \(46)
           (2,26)  (16,28)(23, 45) (35,46) 
                    /       \
               (38)/         \ (35)
               (12 38)     (24,35)
                    
        --------------------------------
          Construct Interval tree
        -------------------------------
          Preorder
          Interval : (22 46) , max 52
          Interval : (3 7) , max 38
          Interval : (2 26) , max 26
          Interval : (16 28) , max 38
          Interval : (12 38) , max 38
          Interval : (33 52) , max 52
          Interval : (23 45) , max 45
          Interval : (24 35) , max 35
          Interval : (35 46) , max 46
        -------------------------------
        */
        // Display tree elements
        System.out.print("\n \n Preorder");
        tree.preorder(tree.root);
        // Search interval
        int low = 10;
        int high = 21;
        IntervalNode ans = tree.overlapSearch(tree.root, low, high);
        if (ans != null)
        {
            System.out.print("\n Search Interval (" + low + "," + 
                             high + ") at (" + ans.low + "," + ans.high + ")");
        }
        else
        {
            System.out.print("\n Search Interval (" 
                             + low + "," + high + ") : None");
        }
    }
}

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program
    Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
    public:
    // Interval keys
    int low;
    int high;
    // Max of child
    int max;
    IntervalNode *left;
    IntervalNode *right;
    IntervalNode(int intervalInfo[])
    {
        this->low = intervalInfo[0];
        this->high = intervalInfo[1];
        this->max = intervalInfo[1];
        this->left = NULL;
        this->right = NULL;
    }
};
class IntervalTree
{
    public: IntervalNode *root;
    IntervalTree()
    {
        this->root = NULL;
    }
    // This is creates and returns the new Interval tree Node node
    void addNode(int intervalInfo[])
    {
        IntervalNode *node = new IntervalNode(intervalInfo);
        if (this->root == NULL)
        {
            // First node
            this->root = node;
            return;
        }
        IntervalNode *auxilary = this->root;
        // Add a Interval node into tree
        while (auxilary != NULL)
        {
            if (auxilary->max < node->max)
            {
                // Change ancestor with new max value
                auxilary->max = node->max;
            }
            if (node->low < auxilary->low)
            {
                if (auxilary->left == NULL)
                {
                    // Add new node
                    auxilary->left = node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    auxilary = auxilary->left;
                }
            }
            else
            {
                if (auxilary->right == NULL)
                {
                    // Add new node
                    auxilary->right = node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    auxilary = auxilary->right;
                }
            }
        }
    }
    // Display preorder of interval tree
    void preorder(IntervalNode *node)
    {
        if (node != NULL)
        {
            cout << "\n Interval : (" 
                 << node->low << " " 
                 << node->high << ") , max " 
                 << node->max;
            // Visit left and right subtree using recursively
            this->preorder(node->left);
            this->preorder(node->right);
        }
    }
    IntervalNode *overlapSearch(IntervalNode *node, int low, int high)
    {
        if (node == NULL)
        {
            return NULL;
        }
        if (node->low <= high && low <= node->high)
        {
            // When resultant node found
            return node;
        }
        if (node->left != NULL && node->left->max >= low)
        {
            return this->overlapSearch(node->left, low, high);
        }
        else
        {
            return this->overlapSearch(node->right, low, high);
        }
    }
};
int main()
{
    IntervalTree *tree = new IntervalTree();
    // Given intervals
    // Note intervals pairs are sorted order
    int intervalValue[][2] = {
        {
            22 , 46
        } , {
            3 , 7
        } , {
            33 , 52
        } , {
            23 , 45
        } , {
            16 , 28
        } , {
            12 , 38
        } , {
            24 , 35
        } , {
            2 , 26
        } , {
            35 , 46
        }
    };
    // Get number of nodes
    int n = sizeof(intervalValue) / sizeof(intervalValue[0]);
    // Add tree element
    for (int i = 0; i < n; ++i)
    {
        tree->addNode(intervalValue[i]);
    }
    /*
                 Max = 52
                 (22, 46)
                /      \
           (38)/        \ (52)
            (3, 7)      (33, 52) 
           /    \        /     \
      (26)/      \(38)  /(45)   \(46)
       (2,26)  (16,28)(23, 45) (35,46) 
                /       \
           (38)/         \ (35)
           (12 38)     (24,35)
                
    --------------------------------
      Construct Interval tree
    -------------------------------
      Preorder
      Interval : (22 46) , max 52
      Interval : (3 7) , max 38
      Interval : (2 26) , max 26
      Interval : (16 28) , max 38
      Interval : (12 38) , max 38
      Interval : (33 52) , max 52
      Interval : (23 45) , max 45
      Interval : (24 35) , max 35
      Interval : (35 46) , max 46
    -------------------------------
    */
    // Display tree elements
    cout << "\n \n Preorder";
    tree->preorder(tree->root);
    // Search interval
    int low = 10;
    int high = 21;
    IntervalNode *ans = tree->overlapSearch(tree->root, low, high);
    if (ans != NULL)
    {
        cout << "\n Search Interval (" 
             << low << "," << high 
             << ") at (" 
             << ans->low << "," 
             << ans->high << ")";
    }
    else
    {
        cout << "\n Search Interval (" 
             << low << "," 
             << high << ") : None";
    }
    return 0;
}

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
package main
import "fmt"
/*
    Go Program
    Construct interval tree
*/
// Interval Tree node
type IntervalNode struct {
    // Interval keys
    low int
    high int
    // Max of child
    max int
    left * IntervalNode
    right * IntervalNode
}
func getIntervalNode(intervalInfo [] int ) * IntervalNode {
    var me *IntervalNode = &IntervalNode {}
    me.low = intervalInfo[0]
    me.high = intervalInfo[1]
    me.max = intervalInfo[1]
    me.left = nil
    me.right = nil
    return me
}
type IntervalTree struct {
    root * IntervalNode
}
func getIntervalTree() * IntervalTree {
    var me *IntervalTree = &IntervalTree {}
    me.root = nil
    return me
}
// This is creates and returns the new Interval tree Node node
func(this *IntervalTree) addNode(intervalInfo[] int) {
    var node * IntervalNode = getIntervalNode(intervalInfo)
    if this.root == nil {
        // First node
        this.root = node
        return
    }
    var auxilary * IntervalNode = this.root
    // Add a Interval node into tree
    for (auxilary != nil) {
        if auxilary.max < node.max {
            // Change ancestor with new max value
            auxilary.max = node.max
        }
        if node.low < auxilary.low {
            if auxilary.left == nil {
                // Add new node
                auxilary.left = node
                return
            } else {
                // Visit left subtree
                auxilary = auxilary.left
            }
        } else {
            if auxilary.right == nil {
                // Add new node
                auxilary.right = node
                return
            } else {
                // Visit right subtree
                auxilary = auxilary.right
            }
        }
    }
}
// Display preorder of interval tree
func(this IntervalTree) preorder(node * IntervalNode) {
    if node != nil {
        fmt.Print("\n Interval : (", 
                  node.low, " ", node.high, 
                  ") , max ", node.max)
        // Visit left and right subtree using recursively
        this.preorder(node.left)
        this.preorder(node.right)
    }
}
func(this IntervalTree) overlapSearch(node * IntervalNode, low int, high int) * IntervalNode {
    if node == nil {
        return nil
    }
    if node.low <= high && low <= node.high {
        // When resultant node found
        return node
    }
    if node.left != nil && node.left.max >= low {
        return this.overlapSearch(node.left, low, high)
    } else {
        return this.overlapSearch(node.right, low, high)
    }
}
func main() {
    var tree * IntervalTree = getIntervalTree()
    // Given intervals
    // Note intervals pairs are sorted order
    var intervalValue = [][] int {
        {
            22,
            46,
        }, {
            3,
            7,
        }, {
            33,
            52,
        }, {
            23,
            45,
        }, {
            16,
            28,
        }, {
            12,
            38,
        }, {
            24,
            35,
        }, {
            2,
            26,
        }, {
            35,
            46,
        },
    }
    // Get number of nodes
    var n int = len(intervalValue)
    // Add tree element
    for i := 0 ; i < n ; i++ {
        tree.addNode(intervalValue[i])
    }
    /*
                 Max = 52
                 (22, 46)
                /      \
           (38)/        \ (52)
            (3, 7)      (33, 52) 
           /    \        /     \
      (26)/      \(38)  /(45)   \(46)
       (2,26)  (16,28)(23, 45) (35,46) 
                /       \
           (38)/         \ (35)
           (12 38)     (24,35)
                
    --------------------------------
      Construct Interval tree
    -------------------------------
      Preorder
      Interval : (22 46) , max 52
      Interval : (3 7) , max 38
      Interval : (2 26) , max 26
      Interval : (16 28) , max 38
      Interval : (12 38) , max 38
      Interval : (33 52) , max 52
      Interval : (23 45) , max 45
      Interval : (24 35) , max 35
      Interval : (35 46) , max 46
    -------------------------------
    */
    // Display tree elements
    fmt.Print("\n \n Preorder")
    tree.preorder(tree.root)
    // Search interval
    var low int = 10
    var high int = 21
    var ans * IntervalNode = tree.overlapSearch(tree.root, low, high)
    if ans != nil {
        fmt.Print("\n Search Interval (", low, ",", high, ") at (", 
                  ans.low, ",", ans.high, ")")
    } else {
        fmt.Print("\n Search Interval (", 
                  low, ",", high, ") : None")
    }
}

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
// Include namespace system
using System;
/*
    Csharp Program
    Construct interval tree
*/
// Interval Tree node
public class IntervalNode
{
    // Interval keys
    public int low;
    public int high;
    // Max of child
    public int max;
    public IntervalNode left;
    public IntervalNode right;
    public IntervalNode(int low, int high)
    {
        this.low = low;
        this.high = high;
        this.max = high;
        this.left = null;
        this.right = null;
    }
}
public class IntervalTree
{
    public IntervalNode root;
    public IntervalTree()
    {
        this.root = null;
    }
    // This is creates and returns the new Interval tree Node node
    public void addNode(int low, int high)
    {
        IntervalNode node = new IntervalNode(low, high);
        if (this.root == null)
        {
            // First node
            this.root = node;
            return;
        }
        IntervalNode auxilary = this.root;
        // Add a Interval node into tree
        while (auxilary != null)
        {
            if (auxilary.max < node.max)
            {
                // Change ancestor with new max value
                auxilary.max = node.max;
            }
            if (node.low < auxilary.low)
            {
                if (auxilary.left == null)
                {
                    // Add new node
                    auxilary.left = node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    auxilary = auxilary.left;
                }
            }
            else
            {
                if (auxilary.right == null)
                {
                    // Add new node
                    auxilary.right = node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    auxilary = auxilary.right;
                }
            }
        }
    }
    // Display preorder of interval tree
    public void preorder(IntervalNode node)
    {
        if (node != null)
        {
            Console.Write("\n Interval : (" + node.low + " " + node.high + ") , max " + node.max);
            // Visit left and right subtree using recursively
            this.preorder(node.left);
            this.preorder(node.right);
        }
    }
    public IntervalNode overlapSearch(IntervalNode node, int low, int high)
    {
        if (node == null)
        {
            return null;
        }
        if (node.low <= high && low <= node.high)
        {
            // When resultant node found
            return node;
        }
        if (node.left != null && node.left.max >= low)
        {
            return this.overlapSearch(node.left, low, high);
        }
        else
        {
            return this.overlapSearch(node.right, low, high);
        }
    }
    public static void Main(String[] args)
    {
        IntervalTree tree = new IntervalTree();
        // Given intervals
        // Note intervals pairs are sorted order
        int[,] intervalValue = {
            {
                22 , 46
            },
            {
                3 , 7
            },
            {
                33 , 52
            },
            {
                23 , 45
            },
            {
                16 , 28
            },
            {
                12 , 38
            },
            {
                24 , 35
            },
            {
                2 , 26
            },
            {
                35 , 46
            }
        };
        // Get number of nodes
        int n = intervalValue.GetLength(0);
        // Add tree element
        for (int i = 0; i < n; ++i)
        {
            tree.addNode(intervalValue[i,0],intervalValue[i,1]);
        }
        /*
                     Max = 52
                     (22, 46)
                    /      \
               (38)/        \ (52)
                (3, 7)      (33, 52) 
               /    \        /     \
          (26)/      \(38)  /(45)   \(46)
           (2,26)  (16,28)(23, 45) (35,46) 
                    /       \
               (38)/         \ (35)
               (12 38)     (24,35)
                    
        --------------------------------
          Construct Interval tree
        -------------------------------
          Preorder
          Interval : (22 46) , max 52
          Interval : (3 7) , max 38
          Interval : (2 26) , max 26
          Interval : (16 28) , max 38
          Interval : (12 38) , max 38
          Interval : (33 52) , max 52
          Interval : (23 45) , max 45
          Interval : (24 35) , max 35
          Interval : (35 46) , max 46
        -------------------------------
        */
        // Display tree elements
        Console.Write("\n \n Preorder");
        tree.preorder(tree.root);
        // Search interval
        int low = 10;
        int high = 21;
        IntervalNode ans = tree.overlapSearch(tree.root, low, high);
        if (ans != null)
        {
            Console.Write("\n Search Interval (" + low + "," + high + ") at (" + ans.low + "," + ans.high + ")");
        }
        else
        {
            Console.Write("\n Search Interval (" + low + "," + high + ") : None");
        }
    }
}

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
<?php
/*
    Php Program
    Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
    // Interval keys
    public $low;
    public $high;
    // Max of child
    public $max;
    public $left;
    public $right;
    public  function __construct($intervalInfo)
    {
        $this->low = $intervalInfo[0];
        $this->high = $intervalInfo[1];
        $this->max = $intervalInfo[1];
        $this->left = NULL;
        $this->right = NULL;
    }
}
class IntervalTree
{
    public $root;
    public  function __construct()
    {
        $this->root = NULL;
    }
    // This is creates and returns the new Interval tree Node node
    public  function addNode($intervalInfo)
    {
        $node = new IntervalNode($intervalInfo);
        if ($this->root == NULL)
        {
            // First node
            $this->root = $node;
            return;
        }
        $auxilary = $this->root;
        // Add a Interval node into tree
        while ($auxilary != NULL)
        {
            if ($auxilary->max < $node->max)
            {
                // Change ancestor with new max value
                $auxilary->max = $node->max;
            }
            if ($node->low < $auxilary->low)
            {
                if ($auxilary->left == NULL)
                {
                    // Add new node
                    $auxilary->left = $node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    $auxilary = $auxilary->left;
                }
            }
            else
            {
                if ($auxilary->right == NULL)
                {
                    // Add new node
                    $auxilary->right = $node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    $auxilary = $auxilary->right;
                }
            }
        }
    }
    // Display preorder of interval tree
    public  function preorder($node)
    {
        if ($node != NULL)
        {
            echo("\n Interval : (".$node->low.
                " ".$node->high.
                ") , max ".$node->max);
            // Visit left and right subtree using recursively
            $this->preorder($node->left);
            $this->preorder($node->right);
        }
    }
    public  function overlapSearch($node, $low, $high)
    {
        if ($node == NULL)
        {
            return NULL;
        }
        if ($node->low <= $high && $low <= $node->high)
        {
            // When resultant node found
            return $node;
        }
        if ($node->left != NULL && $node->left->max >= $low)
        {
            return $this->overlapSearch($node->left, $low, $high);
        }
        else
        {
            return $this->overlapSearch($node->right, $low, $high);
        }
    }
}

function main()
{
    $tree = new IntervalTree();
    // Given intervals
    // Note intervals pairs are sorted order
    $intervalValue = array(
      array(22, 46), array(3, 7), 
      array(33, 52), array(23, 45), 
      array(16, 28), array(12, 38), 
      array(24, 35), array(2, 26), 
      array(35, 46)
    );
    // Get number of nodes
    $n = count($intervalValue);
    // Add tree element
    for ($i = 0; $i < $n; ++$i)
    {
        $tree->addNode($intervalValue[$i]);
    }
    /*
                 Max = 52
                 (22, 46)
                /      \
           (38)/        \ (52)
            (3, 7)      (33, 52) 
           /    \        /     \
      (26)/      \(38)  /(45)   \(46)
       (2,26)  (16,28)(23, 45) (35,46) 
                /       \
           (38)/         \ (35)
           (12 38)     (24,35)
                
    --------------------------------
      Construct Interval tree
    -------------------------------
      Preorder
      Interval : (22 46) , max 52
      Interval : (3 7) , max 38
      Interval : (2 26) , max 26
      Interval : (16 28) , max 38
      Interval : (12 38) , max 38
      Interval : (33 52) , max 52
      Interval : (23 45) , max 45
      Interval : (24 35) , max 35
      Interval : (35 46) , max 46
    -------------------------------
    */
    // Display tree elements
    echo("\n \n Preorder");
    $tree->preorder($tree->root);
    // Search interval
    $low = 10;
    $high = 21;
    $ans = $tree->overlapSearch($tree->root, $low, $high);
    if ($ans != NULL)
    {
        echo("\n Search Interval (".$low.
            ",".$high.
            ") at (".$ans->low.
            ",".$ans->high.
            ")");
    }
    else
    {
        echo("\n Search Interval (".$low.
            ",".$high.
            ") : None");
    }
}
main();

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
/*
    Node JS Program
    Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
    constructor(intervalInfo)
    {
        this.low = intervalInfo[0];
        this.high = intervalInfo[1];
        this.max = intervalInfo[1];
        this.left = null;
        this.right = null;
    }
}
class IntervalTree
{
    constructor()
    {
        this.root = null;
    }
    // This is creates and returns the new Interval tree Node node
    addNode(intervalInfo)
    {
        var node = new IntervalNode(intervalInfo);
        if (this.root == null)
        {
            // First node
            this.root = node;
            return;
        }
        var auxilary = this.root;
        // Add a Interval node into tree
        while (auxilary != null)
        {
            if (auxilary.max < node.max)
            {
                // Change ancestor with new max value
                auxilary.max = node.max;
            }
            if (node.low < auxilary.low)
            {
                if (auxilary.left == null)
                {
                    // Add new node
                    auxilary.left = node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    auxilary = auxilary.left;
                }
            }
            else
            {
                if (auxilary.right == null)
                {
                    // Add new node
                    auxilary.right = node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    auxilary = auxilary.right;
                }
            }
        }
    }
    // Display preorder of interval tree
    preorder(node)
    {
        if (node != null)
        {
            process.stdout.write("\n Interval : (" + 
                                 node.low + " " + node.high + ") , max " +
                                 node.max);
            // Visit left and right subtree using recursively
            this.preorder(node.left);
            this.preorder(node.right);
        }
    }
    overlapSearch(node, low, high)
    {
        if (node == null)
        {
            return null;
        }
        if (node.low <= high && low <= node.high)
        {
            // When resultant node found
            return node;
        }
        if (node.left != null && node.left.max >= low)
        {
            return this.overlapSearch(node.left, low, high);
        }
        else
        {
            return this.overlapSearch(node.right, low, high);
        }
    }
}

function main()
{
    var tree = new IntervalTree();
    // Given intervals
    // Note intervals pairs are sorted order
    var intervalValue = [
        [22, 46],
        [3, 7],
        [33, 52],
        [23, 45],
        [16, 28],
        [12, 38],
        [24, 35],
        [2, 26],
        [35, 46]
    ];
    // Get number of nodes
    var n = intervalValue.length;
    // Add tree element
    for (var i = 0; i < n; ++i)
    {
        tree.addNode(intervalValue[i]);
    }
    /*
                 Max = 52
                 (22, 46)
                /      \
           (38)/        \ (52)
            (3, 7)      (33, 52) 
           /    \        /     \
      (26)/      \(38)  /(45)   \(46)
       (2,26)  (16,28)(23, 45) (35,46) 
                /       \
           (38)/         \ (35)
           (12 38)     (24,35)
                
    --------------------------------
      Construct Interval tree
    -------------------------------
      Preorder
      Interval : (22 46) , max 52
      Interval : (3 7) , max 38
      Interval : (2 26) , max 26
      Interval : (16 28) , max 38
      Interval : (12 38) , max 38
      Interval : (33 52) , max 52
      Interval : (23 45) , max 45
      Interval : (24 35) , max 35
      Interval : (35 46) , max 46
    -------------------------------
    */
    // Display tree elements
    process.stdout.write("\n \n Preorder");
    tree.preorder(tree.root);
    // Search interval
    var low = 10;
    var high = 21;
    var ans = tree.overlapSearch(tree.root, low, high);
    if (ans != null)
    {
        process.stdout.write("\n Search Interval (" + 
            low + "," + high + ") at (" + ans.low + "," + ans.high + ")");
    }
    else
    {
        process.stdout.write("\n Search Interval (" + 
                             low + "," + high + ") : None");
    }
}
main();

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
#    Python 3 Program
#    Construct interval tree

#  Interval Tree node
class IntervalNode :
    #  Interval keys
    #  Max of child
    def __init__(self, intervalInfo) :
        self.low = intervalInfo[0]
        self.high = intervalInfo[1]
        self.max = intervalInfo[1]
        self.left = None
        self.right = None
    

class IntervalTree :
    def __init__(self) :
        self.root = None
    
    #  This is creates and returns the new Interval tree Node node
    def addNode(self, intervalInfo) :
        node = IntervalNode(intervalInfo)
        if (self.root == None) :
            #  First node
            self.root = node
            return
        
        auxilary = self.root
        #  Add a Interval node into tree
        while (auxilary != None) :
            if (auxilary.max < node.max) :
                #  Change ancestor with new max value
                auxilary.max = node.max
            
            if (node.low < auxilary.low) :
                if (auxilary.left == None) :
                    #  Add new node
                    auxilary.left = node
                    return
                else :
                    #  Visit left subtree
                    auxilary = auxilary.left
                
            else :
                if (auxilary.right == None) :
                    #  Add new node
                    auxilary.right = node
                    return
                else :
                    #  Visit right subtree
                    auxilary = auxilary.right
                
            
        
    
    #  Display preorder of interval tree
    def preorder(self, node) :
        if (node != None) :
            print("\n Interval : (", 
                  node.low ," ", node.high ,") , max ", 
                  node.max, end = "")
            #  Visit left and right subtree using recursively
            self.preorder(node.left)
            self.preorder(node.right)
        
    
    def overlapSearch(self, node, low, high) :
        if (node == None) :
            return None
        
        if (node.low <= high and low <= node.high) :
            #  When resultant node found
            return node
        
        if (node.left != None and node.left.max >= low) :
            return self.overlapSearch(node.left, low, high)
        else :
            return self.overlapSearch(node.right, low, high)
        
    

def main() :
    tree = IntervalTree()
    #  Given intervals
    #  Note intervals pairs are sorted order
    intervalValue = [
        [22, 46],
        [3, 7],
        [33, 52],
        [23, 45],
        [16, 28],
        [12, 38],
        [24, 35],
        [2, 26],
        [35, 46]
    ]
    #  Get number of nodes
    n = len(intervalValue)
    i = 0
    #  Add tree element
    while (i < n) :
        tree.addNode(intervalValue[i])
        i += 1
    
    #             Max = 52
    #             (22, 46)
    #            /      \
    #       (38)/        \ (52)
    #        (3, 7)      (33, 52) 
    #       /    \        /     \
    #  (26)/      \(38)  /(45)   \(46)
    #   (2,26)  (16,28)(23, 45) (35,46) 
    #            /       \
    #       (38)/         \ (35)
    #       (12 38)     (24,35)
    # --------------------------------
    #  Construct Interval tree
    # -------------------------------
    #  Preorder
    #  Interval : (22 46) , max 52
    #  Interval : (3 7) , max 38
    #  Interval : (2 26) , max 26
    #  Interval : (16 28) , max 38
    #  Interval : (12 38) , max 38
    #  Interval : (33 52) , max 52
    #  Interval : (23 45) , max 45
    #  Interval : (24 35) , max 35
    #  Interval : (35 46) , max 46
    # -------------------------------
    #  Display tree elements
    print("\n \n Preorder", end = "")
    tree.preorder(tree.root)
    #  Search interval
    low = 10
    high = 21
    ans = tree.overlapSearch(tree.root, low, high)
    if (ans != None) :
        print("\n Search Interval (", 
              low ,",", high ,") at (", 
              ans.low ,",", ans.high ,")", end = "")
    else :
        print("\n Search Interval (", 
              low ,",", high ,") : None", end = "")
    

if __name__ == "__main__": main()

input

 Preorder
 Interval : ( 22   46 ) , max  52
 Interval : ( 3   7 ) , max  38
 Interval : ( 2   26 ) , max  26
 Interval : ( 16   28 ) , max  38
 Interval : ( 12   38 ) , max  38
 Interval : ( 33   52 ) , max  52
 Interval : ( 23   45 ) , max  45
 Interval : ( 24   35 ) , max  35
 Interval : ( 35   46 ) , max  46
 Search Interval ( 10 , 21 ) at ( 2 , 26 )
#    Ruby Program
#    Construct interval tree

#  Interval Tree node
class IntervalNode 
    # Define the accessor and reader of class IntervalNode
    attr_reader :low, :high, :max, :left, :right
    attr_accessor :low, :high, :max, :left, :right
    #  Interval keys
    #  Max of child
    def initialize(intervalInfo) 
        self.low = intervalInfo[0]
        self.high = intervalInfo[1]
        self.max = intervalInfo[1]
        self.left = nil
        self.right = nil
    end

end

class IntervalTree 
    # Define the accessor and reader of class IntervalTree
    attr_reader :root
    attr_accessor :root
    def initialize() 
        self.root = nil
    end

    #  This is creates and returns the new Interval tree Node node
    def addNode(intervalInfo) 
        node = IntervalNode.new(intervalInfo)
        if (self.root == nil) 
            #  First node
            self.root = node
            return
        end

        auxilary = self.root
        #  Add a Interval node into tree
        while (auxilary != nil) 
            if (auxilary.max < node.max) 
                #  Change ancestor with new max value
                auxilary.max = node.max
            end

            if (node.low < auxilary.low) 
                if (auxilary.left == nil) 
                    #  Add new node
                    auxilary.left = node
                    return
                else
 
                    #  Visit left subtree
                    auxilary = auxilary.left
                end

            else
 
                if (auxilary.right == nil) 
                    #  Add new node
                    auxilary.right = node
                    return
                else
 
                    #  Visit right subtree
                    auxilary = auxilary.right
                end

            end

        end

    end

    #  Display preorder of interval tree
    def preorder(node) 
        if (node != nil) 
            print("\n Interval : (", 
                  node.low ," ", node.high ,") , max ", node.max)
            #  Visit left and right subtree using recursively
            self.preorder(node.left)
            self.preorder(node.right)
        end

    end

    def overlapSearch(node, low, high) 
        if (node == nil) 
            return nil
        end

        if (node.low <= high && low <= node.high) 
            #  When resultant node found
            return node
        end

        if (node.left != nil && node.left.max >= low) 
            return self.overlapSearch(node.left, low, high)
        else
            return self.overlapSearch(node.right, low, high)
        end

    end

end

def main() 
    tree = IntervalTree.new()
    #  Given intervals
    #  Note intervals pairs are sorted order
    intervalValue = [
        [22, 46],
        [3, 7],
        [33, 52],
        [23, 45],
        [16, 28],
        [12, 38],
        [24, 35],
        [2, 26],
        [35, 46]
    ]
    #  Get number of nodes
    n = intervalValue.length
    i = 0
    #  Add tree element
    while (i < n) 
        tree.addNode(intervalValue[i])
        i += 1
    end

    #             Max = 52
    #             (22, 46)
    #            /      \
    #       (38)/        \ (52)
    #        (3, 7)      (33, 52) 
    #       /    \        /     \
    #  (26)/      \(38)  /(45)   \(46)
    #   (2,26)  (16,28)(23, 45) (35,46) 
    #            /       \
    #       (38)/         \ (35)
    #       (12 38)     (24,35)
    # --------------------------------
    #  Construct Interval tree
    # -------------------------------
    #  Preorder
    #  Interval : (22 46) , max 52
    #  Interval : (3 7) , max 38
    #  Interval : (2 26) , max 26
    #  Interval : (16 28) , max 38
    #  Interval : (12 38) , max 38
    #  Interval : (33 52) , max 52
    #  Interval : (23 45) , max 45
    #  Interval : (24 35) , max 35
    #  Interval : (35 46) , max 46
    # -------------------------------
    #  Display tree elements
    print("\n \n Preorder")
    tree.preorder(tree.root)
    #  Search interval
    low = 10
    high = 21
    ans = tree.overlapSearch(tree.root, low, high)
    if (ans != nil) 
        print("\n Search Interval (", 
              low ,",", high ,") at (", ans.low ,",", ans.high ,")")
    else
 
        print("\n Search Interval (", 
              low ,",", high ,") : None")
    end

end

main()

input

 
 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
/*
    Scala Program
    Construct interval tree
*/
// Interval Tree node
class IntervalNode(
    // Interval keys
    var low: Int,
    var high: Int,
    // Max of child
    var max: Int,
    var left: IntervalNode,
    var right: IntervalNode)
{
    def this(intervalInfo: Array[Int])
    {
        this(intervalInfo(0),intervalInfo(1),intervalInfo(1), null,null);
    }
}
class IntervalTree(var root: IntervalNode)
{
    def this()
    {
        this(null);
    }
    // This is creates and returns the new Interval tree Node node
    def addNode(intervalInfo: Array[Int]): Unit = {
        var node: IntervalNode = new IntervalNode(intervalInfo);
        if (this.root == null)
        {
            // First node
            this.root = node;
            return;
        }
        var auxilary: IntervalNode = this.root;
        // Add a Interval node into tree
        while (auxilary != null)
        {
            if (auxilary.max < node.max)
            {
                // Change ancestor with new max value
                auxilary.max = node.max;
            }
            if (node.low < auxilary.low)
            {
                if (auxilary.left == null)
                {
                    // Add new node
                    auxilary.left = node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    auxilary = auxilary.left;
                }
            }
            else
            {
                if (auxilary.right == null)
                {
                    // Add new node
                    auxilary.right = node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    auxilary = auxilary.right;
                }
            }
        }
    }
    // Display preorder of interval tree
    def preorder(node: IntervalNode): Unit = {
        if (node != null)
        {
            print("\n Interval : (" + 
                  node.low + " " + node.high + ") , max " + node.max);
            // Visit left and right subtree using recursively
            preorder(node.left);
            preorder(node.right);
        }
    }
    def overlapSearch(node: IntervalNode, 
                      low: Int, 
                      high: Int): IntervalNode = {
        if (node == null)
        {
            return null;
        }
        if (node.low <= high && low <= node.high)
        {
            // When resultant node found
            return node;
        }
        if (node.left != null && node.left.max >= low)
        {
            return overlapSearch(node.left, low, high);
        }
        else
        {
            return overlapSearch(node.right, low, high);
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var tree: IntervalTree = new IntervalTree();
        // Given intervals
        // Note intervals pairs are sorted order
        var intervalValue: Array[Array[Int]] = 
        Array(
          Array(22, 46), 
          Array(3, 7), 
          Array(33, 52), 
          Array(23, 45), 
          Array(16, 28), 
          Array(12, 38), 
          Array(24, 35), 
          Array(2, 26), 
          Array(35, 46)
        );
        // Get number of nodes
        var n: Int = intervalValue.length;
        var i: Int = 0;
        // Add tree element
        while (i < n)
        {
            tree.addNode(intervalValue(i));
            i += 1;
        }
        /*
                     Max = 52
                     (22, 46)
                    /      \
               (38)/        \ (52)
                (3, 7)      (33, 52) 
               /    \        /     \
          (26)/      \(38)  /(45)   \(46)
           (2,26)  (16,28)(23, 45) (35,46) 
                    /       \
               (38)/         \ (35)
               (12 38)     (24,35)
                    
        --------------------------------
          Construct Interval tree
        -------------------------------
          Preorder
          Interval : (22 46) , max 52
          Interval : (3 7) , max 38
          Interval : (2 26) , max 26
          Interval : (16 28) , max 38
          Interval : (12 38) , max 38
          Interval : (33 52) , max 52
          Interval : (23 45) , max 45
          Interval : (24 35) , max 35
          Interval : (35 46) , max 46
        -------------------------------
        */
        // Display tree elements
        print("\n \n Preorder");
        tree.preorder(tree.root);
        // Search interval
        var low: Int = 10;
        var high: Int = 21;
        var ans: IntervalNode = tree.overlapSearch(tree.root, low, high);
        if (ans != null)
        {
            print("\n Search Interval (" + low + "," + high + ") at (" + ans.low + "," + ans.high + ")");
        }
        else
        {
            print("\n Search Interval (" + low + "," + high + ") : None");
        }
    }
}

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)
import Foundation;
/*
    Swift 4 Program
    Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
    // Interval keys
    var low: Int;
    var high: Int;
    // Max of child
    var max: Int;
    var left: IntervalNode? ;
    var right: IntervalNode? ;
    init(_ intervalInfo: [Int])
    {
        self.low = intervalInfo[0];
        self.high = intervalInfo[1];
        self.max = intervalInfo[1];
        self.left = nil;
        self.right = nil;
    }
}
class IntervalTree
{
    var root: IntervalNode? ;
    init()
    {
        self.root = nil;
    }
    // This is creates and returns the new Interval tree Node node
    func addNode(_ intervalInfo: [Int])
    {
        let node = IntervalNode(intervalInfo);
        if (self.root == nil)
        {
            // First node
            self.root = node;
            return;
        }
        var auxilary = self.root;
        // Add a Interval node into tree
        while (auxilary  != nil)
        {
            if (auxilary!.max < node.max)
            {
                // Change ancestor with new max value
                auxilary!.max = node.max;
            }
            if (node.low < auxilary!.low)
            {
                if (auxilary!.left == nil)
                {
                    // Add new node
                    auxilary!.left = node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    auxilary = auxilary!.left;
                }
            }
            else
            {
                if (auxilary!.right == nil)
                {
                    // Add new node
                    auxilary!.right = node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    auxilary = auxilary!.right;
                }
            }
        }
    }
    // Display preorder of interval tree
    func preorder(_ node: IntervalNode? )
    {
        if (node  != nil)
        {
            print("\n Interval : (", 
                  node!.low ," ", node!.high ,") , max ", 
                  node!.max, terminator: "");
            // Visit left and right subtree using recursively
            self.preorder(node!.left);
            self.preorder(node!.right);
        }
    }
    func overlapSearch(_ node: IntervalNode? , 
                       _ low : Int, _ high: Int) -> IntervalNode?
    {
        if (node == nil)
        {
            return nil;
        }
        if (node!.low <= high && low <= node!.high)
        {
            // When resultant node found
            return node;
        }
        if (node!.left  != nil && node!.left!.max >= low)
        {
            return self.overlapSearch(node!.left, low, high);
        }
        else
        {
            return self.overlapSearch(node!.right, low, high);
        }
    }
}
func main()
{
    let tree = IntervalTree();
    // Given intervals
    // Note intervals pairs are sorted order
    let intervalValue = [
        [22, 46],
        [3, 7],
        [33, 52],
        [23, 45],
        [16, 28],
        [12, 38],
        [24, 35],
        [2, 26],
        [35, 46]
    ];
    // Get number of nodes
    let n = intervalValue.count;
    var i = 0;
    // Add tree element
    while (i < n)
    {
        tree.addNode(intervalValue[i]);
        i += 1;
    }
    /*
                 Max = 52
                 (22, 46)
                /      \
           (38)/        \ (52)
            (3, 7)      (33, 52) 
           /    \        /     \
      (26)/      \(38)  /(45)   \(46)
       (2,26)  (16,28)(23, 45) (35,46) 
                /       \
           (38)/         \ (35)
           (12 38)     (24,35)
                
    --------------------------------
      Construct Interval tree
    -------------------------------
      Preorder
      Interval : (22 46) , max 52
      Interval : (3 7) , max 38
      Interval : (2 26) , max 26
      Interval : (16 28) , max 38
      Interval : (12 38) , max 38
      Interval : (33 52) , max 52
      Interval : (23 45) , max 45
      Interval : (24 35) , max 35
      Interval : (35 46) , max 46
    -------------------------------
    */
    // Display tree elements
    print("\n \n Preorder", terminator: "");
    tree.preorder(tree.root);
    // Search interval
    let low = 10;
    let high = 21;
    let ans = tree.overlapSearch(tree.root, low, high);
    if (ans  != nil)
    {
        print("\n Search Interval (", 
              low ,",", high ,") at (", 
              ans!.low ,",", ans!.high ,")", 
              terminator: "");
    }
    else
    {
        print("\n Search Interval (", 
              low ,",", high ,") : None", 
              terminator: "");
    }
}
main();

input

 Preorder
 Interval : ( 22   46 ) , max  52
 Interval : ( 3   7 ) , max  38
 Interval : ( 2   26 ) , max  26
 Interval : ( 16   28 ) , max  38
 Interval : ( 12   38 ) , max  38
 Interval : ( 33   52 ) , max  52
 Interval : ( 23   45 ) , max  45
 Interval : ( 24   35 ) , max  35
 Interval : ( 35   46 ) , max  46
 Search Interval ( 10 , 21 ) at ( 2 , 26 )
/*
    Kotlin Program
    Construct interval tree
*/
// Interval Tree node
class IntervalNode
{
    // Interval keys
    var low: Int;
    var high: Int;
    // Max of child
    var max: Int;
    var left: IntervalNode ? ;
    var right: IntervalNode ? ;
    constructor(intervalInfo: Array < Int > )
    {
        this.low = intervalInfo[0];
        this.high = intervalInfo[1];
        this.max = intervalInfo[1];
        this.left = null;
        this.right = null;
    }
}
class IntervalTree
{
    var root: IntervalNode ? ;
    constructor()
    {
        this.root = null;
    }
    // This is creates and returns the new Interval tree Node node
    fun addNode(intervalInfo: Array < Int > ): Unit
    {
        val node: IntervalNode = IntervalNode(intervalInfo);
        if (this.root == null)
        {
            // First node
            this.root = node;
            return;
        }
        var auxilary: IntervalNode ? = this.root;
        // Add a Interval node into tree
        while (auxilary != null)
        {
            if (auxilary.max < node.max)
            {
                // Change ancestor with new max value
                auxilary.max = node.max;
            }
            if (node.low < auxilary.low)
            {
                if (auxilary.left == null)
                {
                    // Add new node
                    auxilary.left = node;
                    return;
                }
                else
                {
                    // Visit left subtree
                    auxilary = auxilary.left;
                }
            }
            else
            {
                if (auxilary.right == null)
                {
                    // Add new node
                    auxilary.right = node;
                    return;
                }
                else
                {
                    // Visit right subtree
                    auxilary = auxilary.right;
                }
            }
        }
    }
    // Display preorder of interval tree
    fun preorder(node: IntervalNode ? ): Unit
    {
        if (node != null)
        {
            print("\n Interval : (" + 
                  node.low + " " + node.high + ") , max " + node.max);
            // Visit left and right subtree using recursively
            this.preorder(node.left);
            this.preorder(node.right);
        }
    }
    fun overlapSearch(node: IntervalNode ? , low : Int, high: Int): IntervalNode ?
    {
        if (node == null)
        {
            return null;
        }
        if (node.low <= high && low <= node.high)
        {
            // When resultant node found
            return node;
        }
        if (node.left != null && node.left!!.max >= low)
        {
            return this.overlapSearch(node.left, low, high);
        }
        else
        {
            return this.overlapSearch(node.right, low, high);
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val tree: IntervalTree = IntervalTree();
    // Given intervals
    // Note intervals pairs are sorted order
    val intervalValue: Array < Array < Int >> = 
    arrayOf(
      arrayOf(22, 46), 
      arrayOf(3, 7), 
      arrayOf(33, 52), 
      arrayOf(23, 45), 
      arrayOf(16, 28), 
      arrayOf(12, 38), 
      arrayOf(24, 35), 
      arrayOf(2, 26), 
      arrayOf(35, 46)
    );
    // Get number of nodes
    val n: Int = intervalValue.count();
    var i: Int = 0;
    // Add tree element
    while (i < n)
    {
        tree.addNode(intervalValue[i]);
        i += 1;
    }
    /*
                 Max = 52
                 (22, 46)
                /      \
           (38)/        \ (52)
            (3, 7)      (33, 52) 
           /    \        /     \
      (26)/      \(38)  /(45)   \(46)
       (2,26)  (16,28)(23, 45) (35,46) 
                /       \
           (38)/         \ (35)
           (12 38)     (24,35)
                
    --------------------------------
      Construct Interval tree
    -------------------------------
      Preorder
      Interval : (22 46) , max 52
      Interval : (3 7) , max 38
      Interval : (2 26) , max 26
      Interval : (16 28) , max 38
      Interval : (12 38) , max 38
      Interval : (33 52) , max 52
      Interval : (23 45) , max 45
      Interval : (24 35) , max 35
      Interval : (35 46) , max 46
    -------------------------------
    */
    // Display tree elements
    print("\n \n Preorder");
    tree.preorder(tree.root);
    // Search interval
    val low: Int = 10;
    val high: Int = 21;
    val ans: IntervalNode? = tree.overlapSearch(tree.root, low, high);
    if (ans != null)
    {
        print("\n Search Interval (" + 
              low + "," + high + ") at (" + 
              ans.low + "," + ans.high + ")");
    }
    else
    {
        print("\n Search Interval (" + low + "," + high + ") : None");
    }
}

input

 Preorder
 Interval : (22 46) , max 52
 Interval : (3 7) , max 38
 Interval : (2 26) , max 26
 Interval : (16 28) , max 38
 Interval : (12 38) , max 38
 Interval : (33 52) , max 52
 Interval : (23 45) , max 45
 Interval : (24 35) , max 35
 Interval : (35 46) , max 46
 Search Interval (10,21) at (2,26)

Time Complexity

  • Insertion of a node takes O(log n) time on average, where n is the number of nodes in the tree.
  • Search for overlapping intervals takes O(log n) time on average, with a worst-case time complexity of O(n) if the tree is highly unbalanced.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment