edited by
8,641 views
49 votes
49 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).

  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.
edited by

5 Answers

26 votes
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 by
17 votes
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 votes
1 votes
// 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
0 votes
0 votes

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

 

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

Answer:

Related questions