How to create a recursive TreeGraph

Question

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[4]:

Answer 1

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[4]

Answer 2

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 ;;]]];
   ng = EdgeAdd[VertexAdd[grp, ne[[All, 2]]], ne];
   Graph[VertexList[ng], EdgeList[ng], 
    FilterRules[{opts}, Options[Graph]]]
   ];
func[0, opts : OptionsPattern[]] := Graph[{0}, {}, opts];
func[n_, op : OptionsPattern[]] := 
 First@Nest[{gf[#[[1]], 2^(#[[2]] + 1), op], #[[2]] + 
      1} &, {Graph[{0 <-> 1}, op], -1}, n - 1]

Visualizing:

tab = Framed[#, ImageSize -> {200, 200}] & /@ 
  Table[func[j, GraphLayout -> "RadialDrawing", 
    VertexLabels -> "Name", VertexStyle -> Red], {j, 0, 5}]

I am sure there are nicer ways.