1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Side note: I think that this is impossible by definition, as the definition of Set is that it is order-less. Perhaps you should rephrase it as Sequence. $\endgroup$ – barak manos Dec 17 '15 at 7:45
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.