Binary Tree - Properties of Binary Trees

Properties of Binary Trees

  • The number of nodes in a perfect binary tree can be found using this formula: where is the depth of the tree.
  • The number of nodes in a binary tree of height h is at least and at most where is the depth of the tree.
  • The number of leaf nodes in a perfect binary tree can be found using this formula: where is the depth of the tree.
  • The number of nodes in a perfect binary tree can also be found using this formula: where is the number of leaf nodes in the tree.
  • The number of null links (absent children of nodes) in a complete binary tree of nodes is .
  • The number of internal nodes (non-leaf nodes) in a Complete Binary Tree of nodes is .
  • For any non-empty binary tree with leaf nodes and nodes of degree 2, .
Proof:
Let n = the total number of nodes
B = number of branches
n0, n1, n2 represent the number of nodes with no children, a single child, and two children respectively.
B = n - 1 (since all nodes except the root node come from a single branch)
B = n1 + 2*n2
n = n1+ 2*n2 + 1
n = n0 + n1 + n2
n1+ 2*n2 + 1 = n0 + n1 + n2 ==> n0 = n2 + 1

Read more about this topic:  Binary Tree

Famous quotes containing the words properties of, properties and/or trees:

    “The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
    —John Locke (1632–1704)

    “A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
    —Ralph Waldo Emerson (1803–1882)

    “Though trees turn bare and girls turn wives,
    We shall afford our costly seasons;
    There is a gentleness survives
    That will outspeak and has its reasons.
    There is a loveliness exists,
    Preserves us, not for specialists.”
    —William Dewitt Snodgrass (b. 1926)