1
$\begingroup$

I am considering binary trees (tree with at $\textbf{most}$ two children) $ where any 'left' and 'right' children components are considered distinct from each other. I simply want to understand the origin of the equation below as it helps me to understand other aspects of counting trees, and I use this equation a lot throughout my studies

Let $a_h$ be the number of possible distinct binary trees with height (tree level) of h, i.e. where $a_0=1, a_1=3 , a_2=21$ etc.

I want to show that $a_n=2a_{n-1}(1+a_0+a_1+a_2+...+a_{n-2})+a_{n-1}^2$ for all n $\geq$ 2.

$\textbf{My thoughts so far}$

I have been trying to logically describe how and why the number of possible trees of height h depends completely on how many possible trees there are for each of the previous generations in some way or another (like the above equation is showing) but I am struggling to directly match what the equation is saying with my own approach.

I am thinking along the lines of: the 2 in the equation must correspond to the fact that for any unique tree of height h-1, at any node you may add up to two more 'right and or left' nodes to make a unique tree of height h. This as well as realizing the nature of each previous set of unique trees of heights h-i all must directly influence how many there will be of h.

I am considering things like if you can add verticies to a leaf node on a tree of height h-1 to then make a tree of height h, how many ways can you do this, wnad what other ways are there to consider to make all possible height/level h trees such that the above equation can be yielded.

Any guidance would be appreciated.

$\endgroup$
  • $\begingroup$ If the tree's height is $n$ what is the height of the left child ? $\endgroup$ – Youem Apr 21 '18 at 17:09
  • $\begingroup$ By left child, I just mean of the two potential children any node can have, the left child is the branch that goes left. It is simply to say that any two children of any node are unique from each other so I'm not sure if what you're saying makes sense in this context $\endgroup$ – Abraham Merriweather Apr 21 '18 at 17:13
  • $\begingroup$ What I wanted to say is that when you have a tree of height $n$, it has two children one of the children has to have the height $n-1$ this will help you to prove the recursion. $\endgroup$ – Youem Apr 21 '18 at 17:25
  • $\begingroup$ Ah you are referring to children being the entire left or right sub-trees of a tree, i.e. the entire tree split into two at the root vertex? My apologies if I am getting this wrong but I am considering children as any child of any vertex in the tree. If that's what you mean then my thinking is: The $2a_{h-1}$ part means that for every tree of level h-1, there are an additional two ways to extend the tree into one of level h, i.e. by adding a vertex to the say the left sub-tree and one to the right sub-tree (if it was the left sub-tree with h-1 verticies) and vise versa for right case? $\endgroup$ – Abraham Merriweather Apr 21 '18 at 17:33
  • $\begingroup$ Can you see now what you have to do ? $\endgroup$ – Youem Apr 21 '18 at 17:34
1
$\begingroup$

This problem is naturally recursive (or "inductive" if you are not a CS person). Suppose you know the number of distinct binary trees with height $k$, for every $k<n$ Call this quantity $t_k$. To figure out $t_{n}$, consider the following procedure. Take any binary tree $T_{1}$ rooted at some node $r_1$ having height $k_{1}=n-1$, and some other binary tree $T_{2}$ rooted at node $T_{2}$ having height $0\leq k_{2}\leq n-1$. Add a new node $r$ that is adjacent to $r_1$ and $r_2$, the resulting tree is a binary tree of height $n$.

Since we consider the left and right subtree to be distinct, for each tree $T$ we produce, we can place $T_{1}$ as the right child or left child of $r$, so we get a factor of 2 here, except for the case where $T_{1}$ and $T_{2}$ are identical.

So, overall we can choose $T_{1}$ to be any binary tree of height $n-1$, of which there are $t_{n-1}$ such trees, and if we let $T_2$ be a binary tree of height at most $n-2$ then $T_{1}$ and $T_{2}$ are guaranteed to be distinct, so we have $$t_{n-1}(1+t_0+t_1+\dots +t_{n-2})$$ ways to do this, and for every such way, we can swap the positions of $T_{1}$ and $T_{2}$ resulting in a factor of two increase. Note that the 1 comes from the fact that we can choose $T_2$ or $T_1$ to be the empty tree.

For the case where $k_1=k_2=n-1$, we have $(t_{n-1})^2$ ways to choose $T_1$ and $T_2$ So, we have $(t_{n-1}^2)$ ways to choose such trees. All together, we get

$$t_{n}=2t_{n-1}(1+t_0+t_1+\dots +t_{n-2})+t_{n-1}^2$$

$\endgroup$
  • $\begingroup$ The reason I am saying in this case $a_1=3$, and not $a_1=1$, is because here left and right 'single branches' out of a vertex are considered to be different from each other. $\textbf{Trees with height one in this case:} Root node with either: single left child, single right child, both a right and left child. i.e. three possibilities, I'm not sure what you mean by there only being one as in this particular case what I said applies. $\endgroup$ – Abraham Merriweather Apr 21 '18 at 18:21
  • $\begingroup$ a single branch would not give you a binary tree though (the root would have degree 1). If you only care about trees where each node has degree at most two, then you should specify that in your question description $\endgroup$ – mm8511 Apr 21 '18 at 18:23
  • $\begingroup$ This is a binary tree such that each vertex can have at $\textbf{most}$ two children. So the root having just one child (left or right orientated) is allowed. Apologies, I should have been more clear in my description. $\endgroup$ – Abraham Merriweather Apr 21 '18 at 18:25
  • $\begingroup$ Okay, I was confused with a full binary tree. In this case, your formula is correct. $\endgroup$ – mm8511 Apr 21 '18 at 18:29
  • $\begingroup$ Edited my answer to reflect this $\endgroup$ – mm8511 Apr 21 '18 at 18:31

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.