• Status: Solved
• Priority: Medium
• Security: Public
• Views: 3110

# recurrence relation for binary tree height algorithm?

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
melissak
• 3
• 2
• 2
• +2
1 Solution

Commented:
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 Commented:
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

Commented:
Are you assuming the tree is balanced?
0

Author Commented:
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

Commented:
so is C(n) supposed to be the worst case height of a balanced tree of n nodes?
0

Commented:
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

Commented:
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

Commented:
may be (i don't sure)
c(n+1) = C(n) + 1
0

Author Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.