6,795 views

Suppose there is a balanced binary search tree with $n$ nodes, where at each node, in addition to the key, we store the number of elements in the sub tree rooted at that node.

Now, given two elements $a$ and $b$, such that $a < b$, we want to find the number of elements $x$ in the tree that lie between $a$ and $b$, that is, $a \leq x \leq b$. This can be done with (choose the best solution).

1. $O(\log n)$  comparisons and $O(\log n)$ additions.
2. $O(\log n)$ comparisons but no further additions.
3. $O \left (\sqrt{n} \right )$ comparisons but $O(\log n)$ additions.
4. $O(\log n)$ comparisons but a constant number of additions.
5. $O(n)$ comparisons and $O(n)$ additions, using depth-first- search.

Meaning of addition here is that nummber of elements that we are counting between a  and b
what is the correct answer then?

We first find $a$ in the BST in $O(\log n)$ time. Now there are two possibilities, b can be in the right subtree of $a$ or b can be in the right subtree of any of the parents of $a$. For the first case, we simply search for $b$, in the right subtree of $a$ and at each step we add the number of elements in the left subtree +1 (BST being balanced, this can be retrieved from the depth of the node without any finding method), if we are moving right and simply 1 if we are moving left. When we find $b$, this sum will give as the required number of elements. This requires $O(\log n)$ additions but we can do smarter by doing

$$N(a) - N(\text{LEFT}(a)) - N(\text{RIGHT}(b))$$

where, $N(x)$ denote the no. of elements in the subtree rooted at $x$ and if LEFT(a), RIGHT(b) returning 0 for NULL.

For the second case also we do the same method. But first we find the common ancestor of $a$ and $b$ (possible in $O( \log n)$- say $p$ and also count the no. of nodes in the right subtree of each node from $a$ to $p$ excluding $p$. Now, from $p$ to $a$ we proceed the counting as in the earlier case when $b$ was in the subtree at $a$. So, in the worst case we have to do $O(\log n)$ additions. Here, also we can reduce the no. of additions by doing

$$N(p) - N(\text{LEFT}(a)) - N(\text{RIGHT}(b))$$

where, $N(x)$ denote the no. of elements in the subtree rooted at $x$ and if LEFT(a), RIGHT(b) returning 0 for NULL.

by

edited
Yes, I got it now.

option A seems to be correct. As there could be only 2 possibilities for addition.

1: Add numbers that are in the path from a to b.

2: remove numbers that are not in the path from a to b.

The best algorithm will take the best suitable case for a particular situation and in both cases, it will take O(log n).

@Verma Ashish

@ankitgupta.1729

What is the final answer for this question?

$O(\log n)$ comparisons and $O(\log n)$ additions. The algorithm is :

1. Find $a$ and $b$ : This will take $O(\log n)$ comparisons as tree is balanced BST.

2. Follow path from $a$ to $b$, and along the path, keep adding the required number of nodes to result by looking at number stored at each node. Path length is $O(\log n)$, hence number of additions will also be $O(\log n)$.

If b is not in the subtree of a, we cant get the path using normal BST procedure rt?
We actually look at the number of nodes in the right child of each node in the path on our way up, and the number of nodes in the left child of each node in the path on our way down, but yeah, those are $O(\log n)$ additions and $O(\log n)$ comparisons.
@Arjun, yes we need parent pointer to go up the tree, but we can store parents during searching only.
The parent will be the lowest common ancestor for (a, b) - which will be the rightmost common node in the search paths for a and b rt?
@Arjun Sir,what if it is a binary search tree

Will it be o(n) addition and o(n) comparisons

I can't understand how the addition is O(logn).

Yes https://gateoverflow.in/2073/gate2014-3-39 is a similar question. Here we used traversal to find the sum of the elements between two given limits in O(n) time. How did we do the same in O(log n) time here?

Yes, how $\mathbf{\log n}$ additions?

@ankitgupta.1729

@ in that 2014 GATE question, note that the node structure of the tree is different. Here we store additional info.

// res1 ,res2 and count are global variables initialized to 0

//res_link is a global pointer of type struct node* initialized to NULL

//t->data is the value present in a node

//t->elem is the number of elements in the left and right subtrees of t excluding t

//output is the number of elements between a and b including a and b

//Address of the root node is passed as an argument to fun() and we execute fun1() from fun()

//the function fun() is associated with finding 'a' and function fun1() is associated with finding b

void fun(struct node *t)
{
if(a==(t->data))
{
if(t->right)
{
if(t!=root)
{
res2=t->right->elem+2;
}
else
{
fun1(root->right);
printf("%d",res2+1);
}
}
else
res2=1;
}
else if(a<(t->data))
{
fun(t->left);
if(b>(t->data))
{
res1+=res2;
if(t->right)
res2=t->right->elem+2;
else
res2=1;
if(t==root)
{
res2=1;
if(t->right)
{
fun1(t->right);
printf("%d",res1+res2);
}
else
printf("%d",res1+res2);
}
}
else
{
if(count==0)
{
count=1;
if(res2>1)
{
res2=1;
printf("%d",res1+res2);
}
else
printf("%d",res1+1);
}
}
}
else
fun(t->right);
}

fun1(struct node *t)
{

if(b==(t->data))
{

if(t->left)
res2+=t->left->elem +2;
else
res2+=1;
}
else if(b>(t->data))
{
fun1(t->right);
if(t->left)
res2+=t->left->elem +2;
else
res2+=1;
}
else
fun1(t->left);

}

@arjun sir i have constructed the above code to prove that number of additions and number of comparisions will not exceed log n in the worst case. The time complexity of the above code is O(log n). I request you to take a look at this code and  and verify that option a) is correct

@Arjun  sir

@shrestha

@Happy Mittal

comparisons to find out a and b is o(log n) and its fine..

but a balanced binary search tree can be totally full

what if a is the smallest element and b the largest.

so we have to sum up all n elements right.

how the worst case time to sum no. of elements between a and b is 0(log n)?

### 1 comment

Yes, this is exactly what I am thinking….

1
2
3