Binary Tree

• If every node has either 0 or 2 children, a binary tree is called full.

• If the lowest d-1 levels of a binary tree of height d are filled and level d is partially filled from left to right, the tree is called complete.

• If all d levels of a height-d binary tree are filled, the tree is called perfect.

• A perfect tree of height h has \(2^{h+1} - 1\) nodes.

• In a non-empty, full binary tree, the number of internal nodes is always 1 less than the number of leaves.