# Number of 2-3 trees of depth 4

I have a task to find a number of 2-3 trees... I don't quite know what it means, I'm asked to: find the number of 2-3 trees of depth $4$? Is there a specific way to find number of 2-3 trees of depth $n$?

Thanks!

• I think I would be best to ask for clarification from the one who set this question for you. Nov 25 '17 at 2:26
• Draw them all. Count them.
– Raphael
Nov 25 '17 at 11:33
• I'm guessing the 2-3 trees mean B-trees with the parameters set to 2 and 3 here?
– Raphael
Nov 25 '17 at 11:35

Denote by $T_d$ the number of 2-3 trees of depth at most $d$, so $T_0 = 1$ (the tree consisting of a single node) and $T_1 = 3$ (the tree consisting of a a single node; a root with two children; a root with three children). More generally, a 2-3 tree of depth at most $d$ is either just a single node or consists of a root with two or three children, each of which is a 2-3 tree of depth at most $d-1$. Therefore $T_d = 1 + T_{d-1}^2 + T_{d-1}^3$.
Finally, the number of 2-3 trees of depth exactly $d$ is $T_d - T_{d-1}$. For example, the number of 2-3 trees of depth exactly 1 is $T_1 - T_0 = 3-1 = 2$.
• So, in case of B-trees, where all leaves should be at the same level, it seems your analysis would lead to the recursion $B_0=1$, $B_d = B_{d-1}^2 + B_{d-1}^3$. (?) Nov 25 '17 at 14:17