# Binary search tree with interval as element, simple recursion.

• Recursively add interval [e0, e1):

• case (1), if current tree node `p` is empty, add new node as [e0, e1);
• case (2), if current node `p` is not intersected with [e0, e1), add interval to son of p:
`if (e1 < p->e0) addRange(p->left, e0, e1);`
`if (e0 > p->e1) addRange(p->right, e0, e1);`
• case (3), if current node `p` is intersected with [e0, e1), add the intervals that `p` not covered to sons of p:
`if (e0 < p->e0) addRange(p->left, e0, e0);`
`if (e1 > p->e1) addRange(p->right, p->e1, e1);`

Recursively remove interval [e0, e1):

• case (1), if current tree node `p` is empty, do nothing and return;
• case (2), if current node `p` is not intersected with [e0, e1), remove interval in son of p:
`if (e1 < p->e0) removeRange(p->left, e0, e1);`
`if (e0 > p->e1) removeRange(p->right, e0, e1);`
• case (3), if current node `p` is intersected with [e0, e1):
step one: remove interval that are not covered by `p` in p's sons respectively:
`struct node *l = removeRange(p->left, e0, p->e0);`
`struct node *r = removeRange(p->right, p->e1, e1);`
step two: check whether `p` is fully covered by [e0, e1):
if `p` is not fully covered, just truncate `p` and set its sons respectively:
`if (e1 > p->e0 && e1 < p->e1) { p->e0 = e1; p->left = l;}`
`if (e0 > p->e0 && e0 < p->e1) { p->e1 = e0;p->right = r;}`
if `p` is fully covered, `p` should be deleted, chose a non-empty `l` or `r` and new root node replace `p`:
`if (l == NULL) { p = r; } else { p = right-most son of l }`

Recursively query interval [e0, e1):

• case (1), if current tree node `p` is empty, return false;
• case (2), if current node `p` is not intersected with [e0, e1), add interval to son of p:
`if (e1 < p->e0) queryRange(p->left, e0, e1);`
`if (e0 > p->e1) queryRange(p->right, e0, e1);`
• case (3), if current node `p` is intersected with [e0, e1):
step one: query the intervals that `p` not covered to sons of p:
`if (e0 < p->e0) queryRange(p->left, e0, e0);`
`if (e1 > p->e1) queryRange(p->right, p->e1, e1);`
step two: combine query results of sons:
`return l && r` (`l, r` are initialized as true originally)
``````struct node {
int ends[2];
struct node *left, *right;
};

typedef struct {
struct node *root;

} RangeModule;

RangeModule* rangeModuleCreate() {
RangeModule *obj;
obj = (RangeModule *) malloc(sizeof(RangeModule));
obj->root = NULL;
return obj;
}

struct node *addRange(struct node *p, int end0, int end1) {
if (p == NULL) {
p = (struct node *) malloc(sizeof(struct node));
p->ends[0] = end0;
p->ends[1] = end1;
p->left = p->right = NULL;
return p;
}

if (end1 <= p->ends[0]) {
} else if (end0 >= p->ends[1]){
} else {
if (end0 < p->ends[0])
if (end1 > p->ends[1])
}
return p;
}

void rangeModuleAddRange(RangeModule* obj, int left, int right) {
}

bool queryRange(struct node *p, int end0, int end1) {
if (p == NULL)
return 0;
if (end0 >= p->ends[0] && end1 <= p->ends[1])
return 1;

if (end1 <= p->ends[0])
return queryRange(p->left, end0, end1);
if (end0 >= p->ends[1])
return queryRange(p->right, end0, end1);

bool l = 1, r = 1;
if (end0 < p->ends[0])
l = queryRange(p->left, end0, p->ends[0]);
if (end1 > p->ends[1])
r = queryRange(p->right, p->ends[1], end1);
return l && r;
}

bool rangeModuleQueryRange(RangeModule* obj, int left, int right) {
return queryRange(obj->root, left, right);
}

struct node *removeRange(struct node *p, int end0, int end1) {
if (p == NULL)
return NULL;

if (end1 <= p->ends[0]) {
p->left = removeRange(p->left, end0, end1);
} else if (end0 >= p->ends[1]){
p->right = removeRange(p->right, end0, end1);
} else if (end0 > p->ends[0] && end1 < p->ends[1]) {
struct node *tmp = (struct node *) malloc(sizeof(struct node));
tmp->right = p->right;
tmp->left = NULL;
tmp->ends[0] = end1;
tmp->ends[1] = p->ends[1];
p->right = tmp;
p->ends[1] = end0;

} else {
struct node *l = removeRange(p->left, end0, p->ends[0]);
struct node *r = removeRange(p->right, p->ends[1], end1);
if (end1 > p->ends[0] && end1 < p->ends[1]) {
p->ends[0] = end1;
p->left = l;
} else if (end0 > p->ends[0] && end0 < p->ends[1]) {
p->ends[1] = end0;
p->right = r;
} else {
if (l == NULL)
p = r;
else {
struct node *tmp = l;
while (tmp->right != NULL)
tmp = tmp->right;
tmp->right = r;
p = l;
}
}
}
return p;
}

void rangeModuleRemoveRange(RangeModule* obj, int left, int right) {
obj->root = removeRange(obj->root, left, right);
}

void freeTree(struct node *root) {
if (root == NULL)
return;
freeTree(root->left);
freeTree(root->right);
free(root);
}

void rangeModuleFree(RangeModule* obj) {
freeTree(obj->root);
}
``````

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