2 Metrics

• “Full”: a full tree is a tree such that a node either has no child, or it has the maximum number of children. For a binary tree, it means a node either had 0 or 2 children. Assuming that (N,P) is a k-ary tree (each node can have up to k children), then it is a full tree iff ∀n ∈ N : |{(n,m)|(n,m) ∈ P}|∈{0,k}.
• “Complete”: a complete tree must be a full tree, but every leave must also be n or n − 1 links from the root (for some n ≥ 1).

To facilitate the formalized discussion of completeness, we need to define a path. A path is a tuple p(x₁,x_n) = (x₁,x₂,x₃,…x_n) such that ∀i ∈ [1…n− 1] : (x_i,x_i+1) ∈ P We can further define n = |(x₁,x₂,x₃,…x_n)| to be the number of items in the tuple. We define that ∀n ∈ N : p(n,n) = (n).

Recall that we have already defined the “leaf” predicate L(x) that is true iff x is a leaf. Using these definitions, we can define that a non-empty tree (N,P) rooted at node r is complete iff ∃n ≥ 1 : ∀x ∈ N : (L(x)) ⇒|p(r,x)|∈{n − 1,n}.

We can also define the height h(T_r) of a tree as follows. If the tree only has one node (the root r itself), the height is 1, h(({r},{},{},v)) = 1. An empty tree has a height of 0, h(({},{},{},{})) = 0.

We can recursively define the height of a tree T_r = (N,P_L,P_R,v) rooted at node r as h(T_r) = 1 + max(h(T_rR,h(T_rL)), in which T_rR is the right subtree of r, and T_rL is the left subtree of r.