5. Special trees

Special Trees

A rooted tree is called an $m$-ary tree if every internal vertex has no more than $m$ children.

A rooted tree is called a full $m$-ary tree if every internal vertex has exactly $m$ children.

Binary Trees

A rooted tree is called a full binary tree if every internal vertex has exactly $2$ children: a left child and a right child

graph G {
	label="full binary tree"
	node[shape="point"]
	
	1--2,3
	2--4,5
	5--6,7
}

When we have a full binary tree of height $n$:

• the left and right subtrees of the root are both full binary trees of height $\le n-1$
• at least one of the left and right subtrees of the root is a full binary tree of height $n-1$

Counting vertices and edges of trees

A full binary tree with $n$ internal vertices contains $2n-1$ vertices altogether. Every vertex, except the root, is the child of an internal vertex. Because each of the $n$ internal vertices has $2$ children, there are $2n$ vertices in the tree other than the root.

A full $m$-ary tree with $n$ internal vertices contains $m\cdot n+1$ vertices altogether. Every vertex, except the root, is the child of an internal vertex. Because each of the $n$ internal vertices has $m$ children, there are $m\cdot n$ vertices in the tree other than the root.