Dark Mode

6,795 views

48 votes

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).

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

26 votes

Answer should be (D).

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.

edited
Nov 5, 2019
by Akash Papnai

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).

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).

0

17 votes

$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)$.

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)$.

18

5

0

@Happy Mittal Pragy Agarwal Arjun

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

please help me to clear this point.

1

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?

5

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

2

1 vote

// 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;

res_link=t;

}

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;

res_link=t;

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;

fun1(res_link->right);

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

//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;

res_link=t;

}

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;

res_link=t;

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;

fun1(res_link->right);

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

0 votes

__@Arjun sir__

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)?**

** what's the final answer for additionds and why**