recategorized by
31,151 views
118 votes
118 votes
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 ______.
recategorized by

8 Answers

Best answer
172 votes
172 votes

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 $\text{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. 
edited by
111 votes
111 votes

Here is an example 😊

$L =25 , H = 35$
Inorder: $10,15,20,\underset{L}{\boxed{25}},26,27,28,30,31,32,33,34,\underset{H}{\boxed{35}},36,39,42$

  1. Find $L$ and $H \rightarrow O(\log n)$ time.
  2. Traverse '$m$' elements between '$L$' and  '$H$' $\rightarrow O(m)$ [Traversal algorithm]

Total $\rightarrow  O(m + \log n) $

$\qquad a= 0,b=1,c=1,d=0$

$\qquad 10 + 100 = 110$ Answer

Traversal Algorithm:

  1. Find $L$ using Binary search and keep  $H>node> L$ encountered in the search in a stack.
  2. After finding $L,$ add it to stack as well & initialize $sum = 0$
  3.  Now, for all nodes in the stack, do an inorder traversal starting from their right node and adding the node value to sum. If it is found than stop the algorithm.
  • Node (1) 
    • No Right child; Sum = Sum + Node value $= 0 + 25 = 25.$
  • Node (2)
    • Inorder Traversal from Right Child $\rightarrow  24,28$
    • Sum = sum + inorder Traversal + Node Value $=  (25 + 27 + 28) + 26$
  • Node (3)
    • Inorder Traversal From Right Child $\rightarrow 31,32,33,34,\overset{H}{\bf{35}}\overset{\to \text{Stop Inorder Traversal}}{}$
    • Sum = Sum + Inorder Traversal + Node value
      • $\qquad = 25 + 26 + 24 + 28 + (31 + 32 + 33 + 34 + 35) + 30$
      • $\qquad = 25 + 26 + 24 + 28 + 30 + 31 + 32  + 33 + 34 + 35$  Answer

EDIT :

  1. In Step 1, we need to find only $L$ and not $H.$
  2. In Traversal Algo: Find $L$ using Binary Search and Keep, L< Nodes< H, encountered in the search in the stack.
edited by
25 votes
25 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/

12 votes
12 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
Answer:

Related questions

35 votes
35 votes
5 answers
4
go_editor asked Sep 28, 2014
8,745 views
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$. If $P(.)$ denotes the probability of the event, the maximum value of ...