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.
- Proof:
-
-
- 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 (18031882)
“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 (16321704)
“Why are there trees I never walk under but large and melodious thoughts descend upon me?”
—Walt Whitman (18191892)