Chapter: Object Oriented Programming and Data Structure : Non-Linear Data Structures
Properties of binary trees
Properties of binary trees
• The
number of nodes n in a perfect binary tree can be found using this
formula: n = 2h+1-1
where h
is the depth of the tree.
• The
number of nodes n in a binary tree of
height h is at least n = h + 1 and at most n = 2h+1-1
where h
is the depth of the tree.
• The
number of leaf nodes l in a perfect
binary tree can be found using this formula: l = 2h where h is the depth of
the tree.
• The
number of nodes n in a perfect binary
tree can also be found using this formula: n = 2l-1 where l is the number
of leaf nodes in the tree.
• The
number of null links (i.e., absent children of nodes) in a complete
binary tree of n nodes
is (n+1).
• The
number of internal nodes (i.e., non -leaf nodes or n-l) in a complete binary tree of n nodes is 
n/2 
.
• For any
non -empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 +
1.[6]
Related Topics