We must keep track of two pieces of information to find the location of the
orbits at the nth level: the relative
location of the interval 
and its orientation.
A very convenient way to encode both pieces of data
is through the construction of a binary tree that keeps track of all the
intervals generated by the inverse function, 
.
The quadratic map gives rise to
the ``alternating binary tree'' illustrated in
Figure 2.25(b) [13].
The nth level of the alternating binary tree has 
nodes, which are
labeled from left to right by the sequence
This sequence starts at the left with a zero. It is followed by a
pair of ones, then a pair of zeros, and so on until digits
are written down.
To form the alternating binary tree, we construct the above list of 0s and 1s
from level one to level n and then draw in the pair of lines from each
i-1st level node to the adjacent nodes at the ith level.
Now, to find the symbolic name for the interval at the nth level,
,
we start at the topmost node,
, and follow the path down
the alternating binary tree to the nth level, reading off the appropriate
symbol name at each level along the way. By construction, we see that the
symbolic name read off at the nth level of the tree mimics the location of the
interval containing a period n orbit.
More formally, we identify the set of repeating sequences of period n
in 
with the set of finite strings 
. Let 
denote the fraction between 0 and
giving the order, from left to right, generated by the
alternating binary tree. Further, let 
denote
the integer position
between 0 and 
and
let B denote N in binary form.
It is
not too difficult to show that 
, where 
or 1, and
An application of the ordering relation can be read directly off of Figure 2.25(b) for n = 3 and is presented in Table 2.2.
Table 2.2: Symbolic coordinate for n = 3 from the alternating binary tree.
As expected, the left-most
orbit is the string 
, which corresponds to the period one orbit
at the origin, 
. Less obvious is the position of the other period one
orbit, 
, which occupies the fifth position at the third level.
The itinerary of a periodic orbit is generated by a shift on the repeating
string 
:
In this case, the shift is equivalent to a cyclic permutation of the symbolic string. For instance, there are two period three orbits shown in Table 2.2; their itineraries and positions are
and
So the itinerary of a periodic orbit is generated by cyclic permutations of the symbolic name.
