height


Height of a full binary tree


How to solve below equation for the height of a full binary tree, which contains n number of nodes?
n=2^(h+1)-1
I got the answer as,
n = 2^(h+1)-1
n+(-2^(h+1)+1) = 2^(h+1)-1 + (-2^(h+1)+1)
n-2^(h+1)+1 = 0
h = ln(n+2)/ln(2)
Is this equation solving is correct? If not, How to get h from n = 2^(h+1)-1 equation?
We use "Complete" for a full binary tree so it is called a Complete Binary Tree instead of Full Binary Tree.
Below is the derivation of h from the formula n=2^(h+1)-1
n = 2^(h+1)-1
n + 1 = 2^(h+1)
Taking log base 2 (ln2) of both sides
ln2(n+1) = ln2(2^(h+1))
ln2(n+1) = h+1
ln2(n+1) - 1 = h
or
h = ln2(n+1) - 1
I hope you get it right. Bingo.
Further I think you're not so familiar with the properties of logarithm. I will try to explain it here for you. ln2(8) is read as log 8 base 2. ln2(8) answers 3. How is it calculated? what's the answer of 2^3? it's 8. So we may say that taking a log is inverse of taking power. we can answer simple log problems like ln3(9) = ? , as 3^2 = 9 so ln3(9) results 2. Another example ln10(100) = ?, we know that 10^2 = 100, so ln10(100) = 2. You need to know the log properties for excelling in the course of Data Structures and Algorithms. It helps a lot.
For a binary tree, the height is simply given by log2(n).

Related Links

Re-size the Text and Button/Label in Livecode
Overlay a background image onto the web page
WooCommerce - change price based on product_id, width and height
Susy gallery breaks height for display table and table-cell
Flex Slider full height and width without stretching
mPDF set Height for SetHTMLHeader
How to Set Height of PdfPTable in iTextSharp
Margin not showing with 100% width & height
KO Grid Scrollbars not visible & Display issues
Increase scrollview's element height on clicking it
Using soft keyboard on libgdx for iOS and Android (hides textview)
Fine-uploader - Scaling picture by height
Zurb foundation framework - 100% height grid
Dynamically expanding CollectionView : Height of the CollectionView itself (not the items) changing when adding new items
IE 11 bug, div with height > 1,533,917px display negative computed height and doesnt render
iText setMinimumHeight on splitted cell

Categories

HOME
textwatcher
smartphone
reportportal
deep-linking
hyperledger-fabric
phaser-framework
bro
i2c
sudo
hosts
outlook-web-addins
ndis
xlsx
informatica-powercenter
factor-analysis
badge
katharsis
rhmap
spring-data-neo4j
dd-wrt
read-write
preg-grep
canvasjs
freebase
transient
large-data
xamarin.uitest
ddms
jupyter-console
google-account
finite-element-analysis
encapsulation
openweathermap
archer
jtds
range-v3
ideone
defold
webdatagrid
python-hypothesis
jcreator
master
hspec
push-diffusion
uistackview
gitweb
coordinate-transformation
gmsmapview
anti-cheat
approval-tests
void
throughput
divide-by-zero
apache-mina
gulp-livereload
ejabberd-saas
rhel5
bounds
resource-files
cling
bignum
windows-mobile-6
bigint
cilk-plus
nsmatrix
nscolor
socketstream
hinstance
emacs23
selectonemenu
hashalgorithm
shared-objects
for-xml-path
svn-hooks
hadoop-plugins
windows-controls
writing

Resources

Mobile Apps Dev
Database Users
javascript
java
csharp
php
android
MS Developer
developer works
python
ios
c
html
jquery
RDBMS discuss
Cloud Virtualization
Database Dev&Adm
javascript
java
csharp
php
python
android
jquery
ruby
ios
html
Mobile App
Mobile App
Mobile App