# How to create a recursive TreeGraph

How could I create a recursive tree graph, such as one defined by the following:

A family of trees $T_n$ are defined recursively as follows, for all integers $n \ge 1$.

• The tree $T_1$ consists of a single node.
• The tree $T_2$ consists of two nodes: a root node, with a leaf as its only child.
• The tree $T_n$ for $n \geq 3$ consists of a root node connected to two subtrees below it: the left subtree is $T_{n-1}$, and the right subtree is $T_{n-2}$.

I have tried the following:

Clear[T]
T[n_] := TreeGraph[{n}, {n}, VertexLabels -> "Name"] /; n == 1;
T[n_] := TreeGraph[{n, n - 1}, {n -> n - 1}, VertexLabels -> "Name"] /; n == 2;
T[n_] := TreeGraph[{n, T[n - 1], T[n - 2]}, {n -> T[n - 1], n -> T[n - 2]}, VertexLabels -> "Name"] /; n >= 3;


However, the trees that are drawn are disconnected and look like so when evaluating T: • Did I understand correctly your are looking for a binary tree for n>=3 ? – penguin77 Apr 5 '15 at 22:37

If your are looking for a Binary tree than this may work for you:

 fnBTree[n_] :=
CompleteKaryTree[Sequence @@ # , VertexLabels -> "Name"] &  /@
Join[{{1, 1}, {2, 1}}, Table[{i + 1, 2}, {i, n - 2}]]


Call fnBTree with n=4

fnBTree Just for fun to do recursively in contrast to in-built binary graphs,

e[n_] := {n <-> 2 n, n <-> 2 n + 1};
gf[grp_, n_, opts : OptionsPattern[]] := Module[{vl, ne, ng},
vl = Sort@VertexList[grp];
ne = Flatten[e /@ vl[[-n ;;]]];
Graph[VertexList[ng], EdgeList[ng],
FilterRules[{opts}, Options[Graph]]]
];
func[0, opts : OptionsPattern[]] := Graph[{0}, {}, opts];
func[n_, op : OptionsPattern[]] :=
First@Nest[{gf[#[], 2^(#[] + 1), op], #[] +
1} &, {Graph[{0 <-> 1}, op], -1}, n - 1]


Visualizing:

tab = Framed[#, ImageSize -> {200, 200}] & /@ 