3
$\begingroup$

A binary tree has minimal height if the distance from the root to any point is minimal over all trees (with the same number of nodes). How many trees of minimal height are there? I tried finding this sequence in OEIS with no luck. Clearly for $n = 2^k - 1$ the answer is $1$. I'm also interested in recurrence relations for this number.

Ex. For $n = 4$ there exist $6$ possible trees. $4$ configurations where there are $3$ "top" nodes and $1$ bottom, and $2$ configurations purely on the left/right side of the root.

$\endgroup$
2
  • 1
    $\begingroup$ The first few items are $1, 2, 1, 6, 6, 4, 1$. $\endgroup$
    – CiaPan
    Sep 27, 2017 at 7:20
  • $\begingroup$ That's actually how far I got by hand too. $\endgroup$ Sep 27, 2017 at 7:22

1 Answer 1

1
$\begingroup$

Let's call the function you're looking for $f$. Then we already know that: $f(2^k-1) = 1$ for any $k \in \mathbb{N}$. This correspond to a full binary tree of depth $k$.

Let's also state that $f(0) = 1$, as there is a unique way to create an empty tree ($0$ nodes).

We will now try to find a recurrence relation.

Assume we already know all values of $f(n), \forall n \in \{0, \ldots, 2^k-1 \}$ .

Let's try to compute the value of $f(2^k-1+p)$ for $0 < p < 2^k$.

What happens when adding a $p$ nodes to a minimal tree of $2^k-1$ nodes ? Obviously the depth of the tree must increase. As we are looking for minimal depth trees, it should only increase by $1$. This is because the depth of a minimal tree of $2^{k+1}-1$ nodes is $k+1$ so by removing nodes from such a tree we can create a minimal depth tree of $2^k-1+p$ nodes.

Knowing the new depth we can find a first tree structure:

A 2^k-1+p nodes tree

                      [root]
                      /    \
[2^k-1 nodes sub-tree]      [p-1 nodes sub-tree]

Which is a tree made of a root node, a left sub-tree of size $2^k-1$ and a right sub-tree of size $p-1$. We have $f(2^k-1) \cdot f(p-1)$ ways of creating such tree, $f(2^k-1)$ ways of creating the left sub-tree and $f(p-1)$ ways of creating the right sub-tree.

Now we can create all other tree structures by moving nodes from the left to the right, until we reach the situation where we have only $p-1$ nodes on the left and $ 2^k-1$ nodes on the right.

This means we have:

$$ \begin{align*} f(2^k-1+p) &= f(2^k-1 - 0) \cdot f(p-1 + 0) \\ &+ f(2^k-1 - 1) \cdot f(p-1 + 1) \\ &+ \ldots \\ &+ f(2^k-1 - (2^k-1-(p-1))) \cdot f(p-1 + (2^k-1-(p-1))) \end{align*} $$

Which simplifies as:

$$ f(2^k-1+p) = \sum_{i=0}^{2^k-p}{f(2^k-1-i) \cdot f(p-1+i)} $$

Please note that this is not a usual recurrence relation as you need to first determine $k$ the depth of the tree before applying the formula.

$\endgroup$
4
  • $\begingroup$ please care to explain the downvote ? $\endgroup$
    – fjardon
    Sep 27, 2017 at 14:04
  • $\begingroup$ You're right, although your solution is somehow difficult to absorb; I've had some problem to understand you, too. I've even made a comment about the error in the solution, which eventualy turned out to be an error in my understanding it. Upvoted. $\endgroup$
    – CiaPan
    Sep 29, 2017 at 7:24
  • $\begingroup$ @CiaPan Thank you for your comment. English is not my native language and I may have a hard time expressing ideas with the rigor needed for mathematics. I will try to improve the answer. $\endgroup$
    – fjardon
    Sep 29, 2017 at 7:48
  • $\begingroup$ English isn't my native language, either, so we have a two-layer barrier in communication. Like most of stackexchenge users, I suppose :) $\endgroup$
    – CiaPan
    Sep 29, 2017 at 9:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .