GATE CSE
First time here? Checkout the FAQ!
x
0 votes
97 views

It should be 5 according to me.Pleas explain if they are correct.

asked in Algorithms by Loyal (4.7k points) 18 50
retagged by | 97 views
Delete root. Put 196 as root. Compare it with its two children 120 and 130. Swap 120 and 196. Compare with 140 and 150. Swap 196 and 140. Compare with 180 and 190. Swap 196 and 180. 6 comparisons. Anything wrong with this?
arre..I did a mistake in solving..First time I replaced 130, and then 170. So 5 were coming. Yes u r correct. Thanks  :)

1 Answer

+1 vote
ans is 5 only.
answered by Junior (843 points) 1 2 5
ok..thanks :)
6 is correct ans
can u explain how?
^how to know that which is last level.
first we will exchange 196 and root. Then 120 and 196.Now childeren of 196 are 140 and 150. So, 196 and 140 are exchanged.Now childeren of 196 are 180 and 190. And now finally 196 and 180 are excahnged.We cannot go further so, this is the last level. I think u asked this only?
i m only want 2 say in these type of questions we have an algorithm 2 apply on the problem nd that algorithm yields no of comparisons.
   like here we ll apply delete algorithm on root .
now if u r doing like that just before last level it will require atmost 1 comparison nd for all others 2 comparison.so for this type of procedure every time we need 2 check for last level that ll also increases cost may b in terms of  no.of comparisons.
But at last level here, It is doing two comparisons. We have to just check that the node has two childeren and then compare with them, orelse one child orelse it is a leaf. But these things are had to be done in nearly all tree algorithms, and these steps are not increasing any comparisons here.
acc 2 u is it correct r nt?
Delete root. Put 196 as root. Compare it with its two children 120 and 130. Swap 120 and 196. Compare with 140 and 150. Swap 196 and 140. Compare with 180 and 190. Swap 196 and 180. 6 comparisons.
yes..it is correct according to me.
srry i think u r thinking 5 as corrrect ans
i m explaining abt why 5 is nt correct  
just a conflict.:)
oh..Actually someone cleared it above.. thanks for ur effort :)


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
Top Users Oct 2017
  1. Arjun

    23684 Points

  2. Bikram

    17288 Points

  3. Habibkhan

    9194 Points

  4. srestha

    6486 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5168 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4504 Points

  9. sushmita

    4080 Points

  10. Rishi yadav

    3998 Points


Recent Badges

Nice Comment Pooja Palod
Famous Question Harsh181996
Verified Human ASK
Good Comment Bikram
Good Comment Arjun
Nice Comment Arjun
Famous Question Meenakshi Sharma
Famous Question Meenakshi Sharma
Nice Question smartmeet
Nice Comment Vicky rix
27,426 questions
35,275 answers
84,602 comments
33,523 users