Level, height, m-ary and balanced tree

Level and height

In a rooted tree, the level of a vertex is the length of the unique path from the root to it. The root is at level 0, its children at level 1, and so on. The height of the tree is the maximum level of any vertex (the length of the longest path from the root).

   r            level 0
  / \
 a   b          level 1
/ \    \
c  d    e       level 2    -> height = 2

Full m-ary tree

A rooted tree is an m-ary tree if every internal vertex has at most m children. It is a full m-ary tree if every internal vertex has exactly m children. For m = 2 it is a full binary tree.

If a full m-ary tree has i internal vertices, then it has n = mi + 1 vertices and l = (m − 1)i + 1 leaves. Example: a full binary tree with 3 internal vertices has 2·3 + 1 = 7 vertices and 4 leaves.

Balanced tree

An m-ary tree of height h is balanced if all its leaves are at level h or h − 1. For example, a binary tree with root r, children a and b, and two children c, d under a has leaves b (level 1) and c, d (level 2), with h = 2, so it is balanced. A tree with one leaf at level 1 and another at level 3 is not balanced.

An m-ary tree of height h has at most m^h leaves.