Author |
Topic: master theorem for height of binary tree (Read 1269 times) |
|
srikanth.iiita
Newbie
Posts: 33
|
 |
master theorem for height of binary tree
« on: Mar 22nd, 2010, 9:54am » |
 Quote  Modify
|
can we apply master theorem for finding height of binary tree
??
assume tree is complete ..
if no y
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: master theorem for height of binary tree
« Reply #3 on: Mar 22nd, 2010, 2:33pm » |
Quote Modify
|
Well, in that case, I think you could. But I don't see why you would. if you know the number of nodes and know it's a complete tree, you can just calculate the depth. There is no need for recursion.
And if you don't know the number of nodes, you know that to count them you have to look at each one of them once. No need to apply the master theorem there either.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: master theorem for height of binary tree
« Reply #4 on: Mar 22nd, 2010, 2:51pm » |
Quote Modify
|
But for a complete tree, you just have to go left each time to find the height. Runs in O(log n).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: master theorem for height of binary tree
« Reply #5 on: Mar 22nd, 2010, 4:09pm » |
Quote Modify
|
Oh yeah, I forgot that in addition to all the leaf nodes being on the deepest or second deepest level, the ones on the deepest level are also as leftmost as possible.
|
| « Last Edit: Mar 22nd, 2010, 4:10pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: master theorem for height of binary tree
« Reply #6 on: Mar 22nd, 2010, 4:12pm » |
Quote Modify
|
if Some one asks me the about the complexity of code
i should say its O(n)...( in general )
plz comment
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: master theorem for height of binary tree
« Reply #7 on: Mar 23rd, 2010, 1:11am » |
Quote Modify
|
In general, finding the height of a tree is O(n); in the specific case of a complete tree, it's O(log(n)) if you don't know n, or O(1) if you do know n (because then h=floor(log2(n))+1 )
The problem with applying the master theorem in the general case is that during recursion you don't necessarily split remaining work into equal parts. So you can't fit the formula T(n) = a T(n/b) + f(n). Instead, we have T(n) = T(k) + T(n-k-1) + c, where k is the number of nodes in the left tree, n-k-1 is the number of nodes in the right tree, and c is the (constant) amount of work you do per node. It's easy to see you get T(n) = c n = O(n).
|
| « Last Edit: Mar 23rd, 2010, 1:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print