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:

    “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)

    “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)

    “Out of the woods my Master came,
    Content with death and shame.
    When Death and Shame would woo Him last,
    From under the trees they drew Him last:
    ‘Twas on a tree they slew Him—last
    When out of the woods He came.”
    —Sidney Lanier (1842–1881)