SELD DOUBT WHAT IS DIFFERENCE BETWEEN THESE QUESTIONS

Question

https://gateoverflow.in/2073/gate2014-3-39  

 

https://gateoverflow.in/18749/tifr2010-b-26

 

@Arjun SIR  WE ARE TAKING O(M) IN FIRST CASE (QUESTION IN 2014) BUT WHY LOG(N) IN TIFR QUESTION WHICH ONE IS CORRECt

Comments

what are m and n?

---

Arjun M IS THE NUMBER OF ELEMENTS IN BETWEEN TWO NUMBER GIVEN IN QUESTION IN 2014 

---

yes and N?

---

FOR n:    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.

---

sir actually my doubt is that in 2014 question we are taking O(m)to traverse each  number (i.e m numbers )but in tifr question we  can have same situation like gate 2014 question so here compasrisions are asked but we need to compare these numbers one one by i.e here we also need to traverse the required numbers so why not linear time here???

---

in the answer of gate question, they said O(log n) to find the L and H then O(m) to visit each node.

But i am not able to understand how can they visit those nodes in O(m)

( Note that all those node are not contiguous in terms of access )

 

@eyeamgj

in the TIFR question, they are interested in no.of nodes but not the sum.

and each node also store no.of nodes in subtree along with left and right pointers.

===> O(logn)  comparisons and O(logn) additions.  sufficient,

---

@shaik if there are n elements in a binary tree, what's the time complexity to print all those values?

---

Shaik Masthan can u frame an example for tifr question it will be helpful 

and in gate question someone has mentioned a method using stack to traverse m ements

---

printing the values of nodes is like running traversal methods(In order, preorder etc) which are O(n ) algorithm...

---

if there are n elements in a binary tree, what's the time complexity to print all those values?

with in O(n), we can print them sir.

i understood why you gave this statement sir.

While checking for L or H, i will cut the no need part of the tree.

then it is a Binary tree with m (which are required) nodes ==> O(m)

 

right sir?

---

Yes