Let α‎ = a₁a₂…a_n denote a string, or word, in the set of all Σ‎-words, Σ‎*, and let # be in the alphabet Σ‎. then the position tree T(α‎) for α‎# is a tree whose edges are labelled with elements of

1. (a) T(α‎) has (n+1) leaves labelled

   $$1,2,\dots ,n+1$$
   (see diagram);

2. (b) the sequence of labels on the edges of the path from the root to the leaf labeled i is the substring identifier for position i in α‎#.

Position tree. Tree for 10010 #