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

n₀, n₁, n₂ 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 = n₁ + 2*n₂

n = n₁+ 2*n₂ + 1

n = n₀ + n₁ + n₂

n₁+ 2*n₂ + 1 = n₀ + n₁ + n₂ ==> n₀ = n₂ + 1