MCA(1)-04/Project/03

Name	:	Ashutosh Raghuwanshi
Enrollment Number	:	031795362 (MCA-1 Batch-B)
Course Code	:	CS-04
Course Title	:	Data Structures through 'C' and 'PASCAL'
Assignment Number	:	MCA(1)-04/Project/03

Assignment:

Question 1: Let T be a binary tree with height h and n nodes. Show that
log(n+1)-1<=h<=(n-1)/2
For which values of n and h can the above lower upper bounds of h be attained with equality?

NOTE - In the above question the portion that has been cut is misprinted in the given assignment. We will also prove that the missprinted portion is wrong by proving the rest correct.

Solution:

The Analysis

Before going staright to the equations, let me define the binary tree presizely but perfactly. Binary tree is eather empty or consist of a node called root together with at most two subtrees called the left subtree and the right subtree of the root. According to this definition a binary tree may have less then or equals to two nodes attached to it's root. Let's make table of the maximum nodes possible at a perticular height of the binary tree.

Height (h)	Maximum Nodes Possible in a Binary Tree of this Height (N)
0	1 (`1`)
1	3 (`1+2`)
2	7 (`1+2+4`)
3	15 (`1+2+4+8`)
...	...
h	N (`2⁰+2¹+2²+2³+...+2^h)`

Or we can say that for a tree of height h the maximum number of nodes:

N_h =	i = h	2ⁱ	Equation - (1)
	Σ
	i = 0

This is the sumation of a Geomatric Progration and we know that sumation of T terms of a GP is:

S_T = (a + ar + ar² + ar³ +...+ ar^T-1) =

 a(r^T-1) 
r-1

[for r>1]

After comparing (1 + 2 + 2² + 2³ +...+ 2^h) with GP (a + ar + ar² + ar³ +...+ ar^T-1), we have a=1, T=(h+1) and r=2 so after putting these values in the above equation, we will get:

N_h =	i = h	2ⁱ	=	2^(h+1) - 1 2 - 1	= 2^(h+1) - 1	Equation - (2)
	Σ
	i = 0

The Calculus

Now let a binary tree of height h and n nodes. Since we know that n will always be less then or equal to the maximum number of nodes possible (N_h) in a binary tree of height h. So from Equation - (2) we can say:

n ≤ 2^(h+1)-1 ⇒ n+1 ≤ 2^(h+1) ⇒ log₂(n+1) ≤ (h+1) ⇒ log₂(n+1)-1 ≤ h Equation - (3)

Now, when we know that log₂(n+1)-1 is the minimum possible height of a binary tree, lets talk about the maximum possible height of a binary tree. But before doing so let me define the height of a tree. The height of a tree is the longest path from it's root to a leaf. Now to construct the highest tree with n nodes, we can put all the nodes on a single path so that we can lengthen the path to it's maximum. The height of such a tree will be (n-1) because any path of n nodes always has n-1 branches. So, now we have:

h ≤ (n-1) Equation - (4)

And now, from Equation - (3) and Equation - (4) we have:

log₂(n+1)-1 ≤ h ≤ (n-1)
Or in a different format
log₂(n+1)-1 <= h <= (n-1) Proved

Equality Condition

To get the values of h and n at equality condition we have to assume this:

log₂(n+1)-1 = h = (n-1)
⇒ log₂(n+1)-1 = (n-1)
⇒ log₂(n+1) = n
⇒ (n+1) = 2ⁿ
⇒ n = 1 Equation - (5)

Putting Equation - (5) in the initial condition of equality:

log₂(1+1)-1 = h = (1-1)
⇒ 0 = h = 0 Equation - (6)

From Equation - (5) and (6) we can say that at the condition of equality value of h will be zero and value of n will be one.

Conclusion

This theorem tells us that maximum height possible for a binary tree of 'n' nodes is '(n-1)', while it's minimum possible value is 'log₂(n+1)-1'. In this way we can minimize or maximize the height as per our requirement.

X = ∞ × 0