Reputation: 1407
I have a tree that has the following form:
On the first pictures, the height of the tree is 1 and there are 3 total nodes. 2 for 7 on the next and 3 for 15 for the last one. How can I determine how many number of nodes a tree of this form of l
height will have? Also, what kind of tree is that (is it called something in particular?)?
Upvotes: 4
Views: 885
Reputation: 1
This can also be understood like this.
In case of a perfect binary tree total number of leaf nodes are 2^H (H = Height of the tree)
and total number of internal nodes are 2^H - 1
Hence the total number of nodes will be 2^H + 2^H - 1 which is 2^(H+1) - 1 as mentioned by others.
Hope this will help.
Upvotes: 0
Reputation: 3599
A complete binary tree at depth ‘d’ is the strictly binary tree, where all the leaves are at level d.
So, Suppose a binary tree T of depth d
. Then at most
nodes 2(d+1)-1
n
can be there in T.
2(1+1)-1
=2(2)-1
=4-1
=32(2+1)-1
=2(3)-1
=8-1
=72(3+1)-1
=2(4)-1
=16-1
=15The height(h
) and depth(d
) of a tree (the length of the longest path from the root to leaf node) are numerically equal.
Here's an answer detailing how to compute depth and height.
Upvotes: 2
Reputation: 123
What you're describing sounds like "a perfect binary tree". "a binary tree is a tree data structure in which each node has at most two children" http://en.wikipedia.org/wiki/Binary_tree A perfect tree is "A binary tree with all leaf nodes at the same depth." http://xlinux.nist.gov/dads//HTML/perfectBinaryTree.html
height to maximum number of nodes in perfect binary tree =2^(height+1)-1
number of nodes to minimum height =CEILING(LOG(nodes+1,2)-1,1)
Definitions associated with Binary trees can be found at the Wikipedia wiki cited earlier.
Upvotes: 1
Reputation: 3070
That is a perfect binary tree
You can get the number of node considering this recursive approch:
n(0) = 1
n(l+1) = n(l) + 2^l
so
n(l) = 2^(l+1) - 1
Upvotes: 4
Reputation: 13950
The number of nodes in a complete tree is...
n = 2^(h+1) - 1.
Upvotes: 1