The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
3.9k views
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.
asked in DS by Veteran (99.2k points)
recategorized by | 3.9k views

Just additional information -->

http://codeforces.com/blog/entry/18051

8 Answers

+38 votes
Best answer

In worst case for finding $L$ and $H$ it will take $O(\log n)$ time as the given tree is balanced binary search tree.
Now there are $m$ elements between $L$ and $H$. So to traverse m element it will take $O(m)$ time (traversal algorithm given below). So, total

$O(m+\log n)  \implies a=0, b=1,c=1,d=0$
$\therefore 0+(10 \times 1)+(100 \times 1)+(1000 \times 0)=110$. 


To find all the numbers from $L$ to $H$ we can do an inorder traversal from root and discard all elements before $L$ and after $H$. But this has $O(n)$ time complexity. So, we can do a modification to inorder traversal and combine with binary search as follows:

  1. Find $L$ using binary search and keep all nodes encountered in the search in a stack. 
  2. After finding $L$ add it to stack as well and initialize sum = 0.
  3. Now, for all nodes in stack, do an inorder traversal starting from their right node and adding the node value to sum. If $H$ is found, stop the algorithm. 
answered by Active (2.1k points)
selected by

Point 3, you are saying do inorder traversal starting from the right node until H is encountered. It is for all values encountered in stack. Then i think time complexity will be more.

Sir, the tree is a balanced BST unlike the one you've drawn.

@kalpish, can you elaborate this stack using concept with some example? see this discussion on group.

https://www.facebook.com/groups/core.cs/permalink/1316231181742465

See we can understand like this :

First in order to find number which is labelled L , it will O(logn) time as it is a balanced BST.Then to add the m numbers between L and H , we use the modification of inorder traversal which will hence take O(m) time.Hence the value of a = 0 , b = 1 , c = 1 and d = 0 Hence the answer is 110.

I think while searching L we should not keep all the elements in the stack. Only the elements which are greater than L has to  be kept.
Otherwise we may be adding values smaller than L or sometimes same values more than once.

While searching for 15, we should not add 10 to the stack.

Impeccable explanation! Thanks a lot...
How can we start inorder from L?

anyhow we have to reach L first!
For reaching L log n is time, as explained in answer. Sorry for previous comment stack will be required.
why answer isn't 1100-(c=1,d=1)

Balanced BST takes logn time and for each m element it takes O(mlogn)
For each m element is does not take mlogn.

Search for L in Balanced Binary Search Tree = O(Log n)

Now, start taking inorder elements of the balanced tree, one by one. In each iteration you compare the element you got with L and H. If the element is between L && H then add it to the sum.

Hence, after inorder traversal is complete, you will have the sum (no need to complete inorder traversal till n elements since we are concerned only till m).

Total time taken = Time to search L + inorder Traversal of only m elements

O(logn + m)
+7 votes

int getSum(node *root, int L, int H)
{
   // Base Case
   if (root == NULL)
      return 0;

   if (root->key < L)        
       return getSum(root->right, L, H);

  if (root->key > H)
      return getSum(root->left, L, H)

   if (root->key >= L && root->key <=H)        
      return getSum(root->left, L, H) + root->key +
             getSum(root->right, L, H);
}

it will be O(logn +m)

it can go max of logn depth to find nodes in range and  function calls for nodes in range ie m

Note that the code first traverses across height to find the node which lies in range. Once such a node is found, it recurs for left and right children. Two recursive calls are made only if the node is in range. So for every node that is in range, we make at most one extra call (here extra call means calling for a node that is not in range).

source:http://geeksquiz.com/gate-gate-cs-2014-set-3-question-49/

answered by Boss (8.3k points)
Thanks for valuable effort.
So in worst case 'm' can equal to 'n', right?
+6 votes

Here is an example :)

answered by Loyal (4k points)
Thanks for valuable effort.
@Chhotu

Now, I am having a doubt

Why traversal algo will take O(m) time ? :P

Why traversal algo will take O(m) time ? :P

OK, But first tell me why do you think we can access node > O(m) ?

I am thinking like this :

Maxi. in stack we could have logn nodes

for each of logn nodes we will do inorder traversal on right subtree.

tc=logn +m
Hi @VS ji,

Step (1) of your solution requires small correction( First we are only finding L)

Now for L we are doing in-order traversal of partially visited tree. In-order traversal gives output nodes in sorted order if it is BS-tree. So after traversal of m nodes. you will get your H also. I hope this helps.
VS is fine no need of "ji" or call me Vidhi

I got it :)

In first part we only need to Find L and no need of finding H.
+5 votes
Do tree traversal from root as follows: Do a recursive search to find L, saving all the nodes visited in a stack. Since tree is balanced BST, it'll take O(log n) time. After finding L instead of search do inorder traversal up to m nodes from this node and continuing (if needed) using the saved nodes during searching. Complexity O(m).

Total time = O(m) + O(log n)

a=0, b=1, c=1, d=0
a+10b+100c+1000d = 0+ 10 + 100 + 0
= 110
answered by Veteran (48.3k points)
how to calculate a,b,c,d value?
how the inorder traversal will take o(m) it should take o(n) for n nodes
how are u going to decide that whether m is greater or logn is greater??which one is the dominating factor??

in O(logn) we can find the either L and H, so in inorder sorted list then we can get the m middle elements and their sum in o(m) steps by simple traversal in the list.

but the why isn't the O(n) time for making the inorder traversal being considered in above answer that is to be added, so then the whole answer will change.

 

the better approach seems to be O(mlogn) by simple search of m elements on AVL, then a=0, b=0, c=1 & d=1

and that computes 1100 as the answer

"saving all the nodes visited in a stack."

Why stack is required [email protected] Sir

Cant we do simply like find L in logn time then Visit m elements in inorder until we reach H in O(m) time.??
+1 vote
within those m numbers, we have to search m times to see if the numbers are existing in the Balanced BST & add them.

so, m log n time.

c = 1, d = 1 => answer = 0 + 0 + 100 + 1000 = 1100
answered by (35 points)
out of n elements u r checking for exactly m elements.. but it may b possible m-k elements satisfy condition(less than H greater than L).. For rest K elements again u have to do same thing.. that ll take O(n) time..
@Digvijay

   U r saying "it may b possible m-k elements satisfy condition(less than H greater than L).. For rest K elements again u have to do same thing.. that ll take O(n) time.."

But in the question  it is clearly mentioned  that there are  'm' such numbers. So how will it be m-k . ?

Can u  please explain it.
0 votes

We can firstly do inorder traversal of this Balanced BST which will result in sorted list of elements. It will take O(n).

No we can perform binary search on this sorted list to find L and H. It will take O(logn).

After finding L and H. We will run a loop to sum all elements between L and H. As there are m elements between L and H. So it will take O(m).

So total =O(n)+O(logn)+O(m) {As m<=n and O(n+logn)>=O(n)}

Hence we get O(n)

So a=1,b=0,c=0,d=0

So a+10b+100c+1000d =1+0+0+0=1

I am getting confuse whether I am thinking right or wrong So Please help...

answered by Loyal (2.7k points)
edited by
0 votes
Here in worst case all the elements will be present in the BST for the given no L and H

so T(n)=mlog(n)

after comparing with the given time-complexity we got c=1 ,d=1 a=0,b=0

100*1 + 1000*1 =1100
answered by (159 points)
–1 vote

The answer should be (mlogn).

Because in Balance BST we can search a node in logn time.so l and h can be found in logn time.

In worst case all the m elements will present in the tree.

so we can take each element from m elements and search it and hence total time will be mlogn.

so c = 1 and d = 1

hence a + 10b + 100c + 1000d = 100 + 1000 = 1100

answered by (35 points)
arjun sir is my approach is correct??
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,157 questions
36,985 answers
92,166 comments
34,824 users