CODEWITHSUNDEEP
binary-treeproof
Gayan Jayasingha
Gayan Jayasingha

Reputation: 802

Proof of relationship between nodes (n) and height (h) of Full Binary Tree

I have an assignment that reads as follows

Prove that the relationship between nodes (n) and height (h) of Full Binary Tree is 2^h=(n+1)/2.

I have tried the following:

n = 2^(h+1)-1

n+1 = 2^(h+1)

n+1 = 2^h*2

therefore

2^h=(n+1)/2

I know this cant be that simple. That's why I am asking.

Upvotes: 1

Views: 835

Answers (1)

aioobe
aioobe

Reputation: 420951

From where did you get n = 2^(h+1)-1 ? If you take that formula for granted, there's not much left to prove!

This is type of exercise is typically solved by induction. Here are the steps:

  • Show that it holds for the base case, h = 0. Usually completely trivial.
  • Assume that it holds for a fixed height, i.e. that the formula holds for h = k
  • Show (under the above assumption) that it holds for h = k+1.

Upvotes: 1

Related Questions