Give a recursive definition for the set T.

Question

I am not sure if math stack exchange is the right place to ask about this but I will ask away.

Consider the set T of binary trees that have the following property: For each node in the tree, the heights of that node's left and right subtrees differ at most by 1.

$\textbf{Give a recursive definition for the set T.}$

In the simplest case, $t$ is a tree with a single node. Since it has no subtrees, it follows that there is no difference between the height of its left and the right subtrees.

Im not quite sure how to give the recursive definition on this one. I was initially thinking that it would go something like this: "If there is a tree $t_1$ and $t_2$ satisfying the given property, then a tree t with its root attached to the root of $t_1$ and $t_2$ would also satisfy the property." However, a simple implementation of that definition would show that this is simply not true.

For example, if $t_1$ is a single node tree, and $t_2$ is a tree with height 20 on both the left and right subtrees, the two trees satisfies the given precondition. If a node $t$ connects $t_1$ and $t_2$ in their roots, $t$ would not satisfy the condition

How do I do this?

Answer 1

You can just write it as follows, only replacing "for every node" with an inductive rephrasing:

$T$ is the smallest set of binary trees such that: The tree consisting of a single node belongs to $T$ and: If $t_1, t_2 \in T$ such that the difference of the heights of $t_1$ and $t_2$ is at most $1$, then the tree with has $t_1$ and $t_2$ as its left and right subtrees, also belongs to $T$.