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)

    “At the heart of all beauty lies something inhuman, and these hills, the softness of the sky, the outline of these trees at this very minute lose the illusory meaning with which we had clothed them, henceforth more remote than a lost paradise ... that denseness and that strangeness of the world is absurd.”
    —Albert Camus (1913–1960)