Solved

recurrence relation for binary tree height algorithm?

Posted on 1998-11-10
9
2,855 Views
Last Modified: 2008-02-26
what would the recurrence relation be for the following pseudo code algorithm?

void Height(T)
{
     if (T is not empty)
     {
          lefttreeht = Height(left subtree of T);
          righttreeht = Height(right subtree of T);
         
          if (lefttreeht > righttreeht)
               return lefttreeht + 1;
          else
               return righttreeht + 1;
     }
     else
          return 0;
}

0
Comment
Question by:melissak
  • 3
  • 2
  • 2
  • +2
9 Comments
 
LVL 3

Expert Comment

by:arnond
Comment Utility
do you mean big O complexity ?
if so, it's O(log n), n being the number of nodes in the tree.

Arnon David.
0
 

Author Comment

by:melissak
Comment Utility
No, I mean;

     base case C(0)=0

recurrence relation for a tree of n nodes:

     C(n) = C(n-1) + something or nothing
     C(n+1) = C(n) + something or nothing

*parenthesis indicate subscript

this is what I think the format should somewhat be but
it could be something different.  I do know that the
explicit formula should be:

     C(n)=log(2)[n+1]-1

which was developed from some recurrence relation.
thanks
mk
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Are you assuming the tree is balanced?
0
 

Author Comment

by:melissak
Comment Utility
I don't think it matters.  The definition for the height of a
tree is: the number of nodes on the longest path from the root
to a leaf.  So, worst case binary tree would be one that has nodes attatched to the left or right side only (a diagonal).
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 84

Expert Comment

by:ozo
Comment Utility
so is C(n) supposed to be the worst case height of a balanced tree of n nodes?
0
 
LVL 16

Accepted Solution

by:
heyhey_ earned 100 total points
Comment Utility
maybe i am missing something, but if
the explicit formula should be:
     C(n)=log(2)[n+1]-1
than the recurrence relation should be
     C(n+1)=C(n) + log(2)[n+1]
     
0
 

Expert Comment

by:guga
Comment Utility
I have one comment
if C(n)=log(2)[n+1]-1 then let's n=4

C(n)=log(2)[5]-1;

but height of tree must be integer!
0
 

Expert Comment

by:guga
Comment Utility
may be (i don't sure)
c(n+1) = C(n) + 1
0
 

Author Comment

by:melissak
Comment Utility
I had math student help me.  With each call to the algorithm the list of N elements is halved.  Since the algorithm recursively calls itself twice the formula is:
C(N) = 2*C(N/2)
To Prove relation:
Let N = 2^n

C(2^n) = 2*C(2^n-1)
C(2^n-1) = 2*C(2^n-2)
C(2^n) = 2^k * C(2^n-k)
Let k=n
C(2^n) = 2^n * C(2^0) = 2^n

since 2^n = N

C(N) = N

BigOH = O(N)

sorry took so long to respond.  e-mail and internet down.
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now