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)

    “I do not know but it is too much to read one newspaper a week. I have tried it recently, and for so long it seems to me that I have not dwelt in my native region. The sun, the clouds, the snow, the trees say not so much to me. You cannot serve two masters.”
    —Henry David Thoreau (1817–1862)