The SlugMath Wiki is under heavy development!

# Def/Rooted ordered binary tree

Definition of Composition tree: Let $n$ be a positive natural number. A binary composition tree (or rooted ordered binary tree) with $n$ leaves, is defined recursively as follows:

A composition tree with leaf set $\{a,b,c \}$
• A set $L$ called the set of leaves.
• A set $T$, which is one of the following:
• If $n = 1$, then $L = \{ T \}$.
• If $n > 1$, then there exist positive natural numbers $n_\ell,n_r$ such that:
• $n_\ell + n_r = n$.
• $T = (T_\ell, T_r)$ is an ordered pair.
• There exist subsets $L_\ell, L_r \subset L$, such that:
• $(T_\ell, L_\ell)$ is a binary composition tree with $n_\ell$ leaves.
• $(T_r, L_r)$ is a binary composition tree with $n_r$ leaves.
• $L_\ell \cup L_r = L$.

Binary composition trees $(T,L)$ are visualized as follows:

• One begins with a point, called the root.
• If $T$ is a binary composition tree with one leaf, $L = \{ T \}$, then the root point is labelled by $T$.
• Otherwise, one draws two edges, one left and one right, but both downward from the root.
• At the ends of these edges, one draws the binary composition trees $(T_\ell, L_\ell)$ (at the left), and $(T_r, L_r)$ at the right.
• One continues recursively, until all leaves are reached.

## Logical Connections

This definition logically relies on the following definitions and statements: Def/Natural number, Def/Recursion

The following statements and definitions logically rely on the material of this page: Def/Associative, and Def/Binary operation

To visualize the logical connections between this definition and other items of mathematical knowledge, you can visit any of the following clusters, and click the "Visualize" tab: Clust/Graph theory, Clust/Operations