According to the path, how to draw such a binary tree?

Question

As shown in the figure, the path can be generated by the following code

n=5;
Select[Tuples[{1,2,3},n],#[[1]]==1&&#[[-1]]!=1&&AllTrue[Partition[#,2,1],Unequal@@#&]&]

{{1,2,1,2,3},{1,2,1,3,2},{1,2,3,1,2},{1,2,3,1,3},{1,2,3,2,3},{1,3,1,2,3},{1,3,1,3,2},{1,3,2,1,2},{1,3,2,1,3},{1,3,2,3,2}}

I also know how to draw a binary tree

CompleteKaryTree[n, 2, VertexLabels -> {x_ :> Placed[F[x], Center]}, VertexSize -> 0]

But i don't know how to combine them together.

Answer 1

I would suggest something like this:

n = 5;
paths = Select[Tuples[{1, 2, 3}, n], #[[1]] == 1 && #[[-1]] != 1 && AllTrue[Partition[#, 2, 1], Unequal @@ # &] &]
Graph[
 DeleteDuplicates@Catenate[
   Rule @@@ Partition[Rest@FoldList[Append, {}, #], 2, 1] & /@ paths
   ],
 VertexLabels -> {___, i_} -> i
 ]

This works by effectively labeling each vertex with the path needed to get to it (to avoid confusing the different vertices with the same state). So e.g. the top 1 is {1} and the 3 below that is {1,3}. This is a bit easier to see when using VertexLabels->Automatic:

Answer 2

pathsToGraph = Graph[
    GraphUnion @@ (PathGraph[Extract[#, List /@ Range[Range @ Length @ #]]] & /@ #), 
    ##2 (* graph options *)] &;

Example:

n = 5;
paths = Select[Tuples[{1, 2, 3}, n],
  #[[1]] == 1 && #[[-1]] != 1 && AllTrue[Partition[#, 2, 1], Unequal @@ # &] &];

pathsToGraph[paths, 
  VertexSize -> Large, 
  VertexLabels -> {v_ :> Placed[Last[v], Center]}, 
  VertexStyle -> White]