Skip to main content
add graphs-and-networks tag
Link
halmir
  • 15.3k
  • 37
  • 54
Source Link

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