To construct a symmetric binary tree, choose an angle θ with 0° < θ < 180° and a scaling factor r with 0 < r < 1. Start with a vertical line segment (the trunk) of length 1. The trunk splits into two branches at the top that each form an angle of θ with the linear extension of the trunk, one to the left and one to the right. Each branch has length r. Each of these two branches forms the trunk of a subtree that splits into two more branches following the same rule. The angle is again θ and the length of each of the four new branches is r^{2}. See the illustration below where θ = 60° and r = 0.65.
The symmetric binary tree is obtained by continuing to add more branches ad infinitum, using the angle θ and scaling factor r for each set of new branch segments.
Here are some examples of symmetric binary trees through 12 iterations.
θ=30°, r=0.7
θ=45°, r=0.57
θ=120°, r=0.7
θ=150°, r=0.8
The limit points of the branches in a binary tree are called the branch tips.
Iterated Function System
The two branches are obtained from the trunk by scaling by a factor of r, rotating counterclockswise by θ (left) and −θ (right), then translating to the top of the trunk. The third function needed is the identity. This keeps the branches already drawn in their current locations while the first two functions add the new branches.
Note that function 3 in this iterated function system is not a contractive mapping. Therefore the theory of contractive iterated function systems cannot necessarily be applied here. However, in this case the iterates of an initial set under this iterated function system do converge to a limit set, but the limit will depend on the initial set [Proof]. This type of iterated function system is often called an IFS with condensation.
45° tree thick rectangle as initial set
45° tree unit square as initial set
If only the first two functions are used as the iterated function system, the system will be contractive and all initial sets will converge to the branch tips. Both of the trees above have the same branch tips shown below.
Branch Addresses
The paths of a symmetric binary tree can be addressed by finite strings of the letters L and R, with L corresponding to branching to the left and R corresponding to branching to the right. For example, the image below shows the ends of the paths corresponding to the addresses L, R, LL, LR, RL, and RR. The red branches are drawn to the left and the blue branches are drawn to the right.
The next image shows the first 7 iterations in the construction of a symmetric binary tree. Click on the buttons to the right to see the path corresponding to the button's address.
The branch tips are obtained as infinite sequences of L and R. For example, the sequence (RL)^{∞} = RLRLRL... would be a path alternating right and left branches. Notice the symmetry with the address (LR)^{∞}. The address R^{∞} corresponds to an infinite spiral of right branches.
Self-Contacting Trees
If the scaling factor r is too small, the branches of the tree will be self-avoiding, while if r is too large the branches will overlap. Mandelbrot and Frame showed that for each angle θ, there is a unique scaling factor r_{sc} such that the symmetric binary tree with that θ and r will be self-contacting, that is, branches may touch at a single point but may not cross. In this case, the branch tips of left-side branches will coincide with branch tips of some right-side branches, but no branch tip will coincide with any non-tip point of the tree. Three examples are shown below for θ=60°.
For 0 < θ ≤ 90°, let N_{θ} be the smallest integer such that N_{θ}θ ≥ 90°. On this interval, the value of r_{sc} is the unique solution to the equation
\[
r^2\cdot \left( {\frac{r^{N_\theta+1}\cos((N_\theta-1)\theta)-r^{N_\theta}\cos(N_\theta\theta)-r\cos(\theta)+1}{r^2+1-2r\cos(\theta)}} \right) = \frac{1}{2}.
\]
For 90° ≤ θ < 135°, we have
\[
r_\text{sc} = \frac{1}{\sqrt{2-3\cos^2(\theta)}-\cos(\theta)}
\]
and for 135° ≤ θ < 180°,
\[
r_\text{sc} = -\frac{1}{2\cos(\theta)}
\]
Here is a graph of r_{sc} as a function of θ. We see that \(\frac{1}{2} < r_\text{sc} ≤ \frac{1}{\sqrt{2}}\), with the maximum value occurring at θ = 90° and θ = 135°. The dashed lines occur at 135° and 90°/N for N = 1, 2, 3, 4, 5, 6. There should also be many more dashed lines at θ = 90°/N for N > 6 but they would all begin to run together as N gets larger. These values reflect the change in N_{θ} in the equation for r_{sc} for 0° < θ < 90°.
See a catalog of all self-contacting symmetric binary trees for integer angles from 1° to 179° by clicking on the Play button below. There will be a slight pause at θ=90° (tree is a filled in rectangle) and at θ=135° (tree is a filled in triangle) corresponding to the two transition values in the graph of r_{sc} above.
Similarity Dimension (Branch Tips)
When r ≤ r_{sc}, the branch tips form a fractal that is self-similar with 2 non-overlapping copies of itself, each scaled by the factor r < 1. Therefore the similarity dimension, d, of the attractor of the IFS corresponding to the branch tips is the solution to
\[
\sum_{k=1}^2 r^d = 1 \quad \Rightarrow \quad d = \frac{\log(1/2)}{\log(r)} = -\frac{\log(2)}{\log(r)}
\]
Click on the buttons to the left for some examples of branch tips of self-contracting trees and their dimensions.
Here is a graph of the similarity dimension of the branch tips of the self-contacting trees (r = r_{sc}).
Let the tree be defined by the angle θ and scaling factor r. We will take the base of the tree to be at the origin and the initial vertical trunk to be of length 1. By the "top" of the tree we will mean the top of the branch tips, that is, the largest y-coordinate of the branch tips. The "bottom" of the tree will mean the bottom of the branch tips, that is, the smallest y-coordinate of the branch tips. The "right side" of the tree will be the largest x-coordinate of the branch tips (and by symmetry, the left side will be the negative of this x-coordinate.) For most symmetric binary trees, the top of the tree will correspond to the y-coordinate of the branch tip of the path (LR)^{∞}, or equivalently (RL)^{∞} = R(LR)^{∞}; the right side will correspond to the x-coordinate of the branch tip of the path R^{k}(LR)^{∞} where k is the smallest integer with kθ ≥ 90°; and the bottom will correspond to the y-coordinate of the branch tip of the path R^{k}(LR)^{∞} where k is the smallest integer with kθ ≥ 180°.
θ = 35°, r = 0.6
blue = right branch, red = left branch
top = 2.6539, side = 1.51964, bottom = 1.15588
As observed by Don West for the top of the tree, however, the branch tip for (LR)^{∞} or (RL)^{∞} may not always have the largest y-coordinate. Indeed, for every θ that is not of the form 360°/n for some integer n, there will be a critical value r_{T} such that if r > r_{T}, then the branch tip for the path R^{k}(LR)^{∞}, or equivalently, L^{k}(RL)^{∞}, will have a greater y-coordinate, where k is the smallest integer such that kθ ≥ 360°.These scaling factors will be fairly large, however, and the resulting binary trees will have massively overlapping branches as shown in the example below.
θ = 150°, r = 0.8
Similar exceptions hold for the bottom and sides of a binary tree for certain intervals of θ. None of these exceptions will happen, however, for self-contacting trees or when r < r_{sc}. For these trees, the top, bottom, and sides will always be determined by the paths described in the first paragraph. Click for the mathematical details.
Special Properties
Golden Symmetric Binary Trees
Tara Taylor has studied the four self-contacting symmetric binary trees for which the scaling factor is equal to \(\frac{1}{\phi}\), where \(\phi = \frac{1+\sqrt{5}}{2}\) is the golden ratio. These four trees correspond to the angles 60°, 108°, 120°, and 144° [Proof]. For details about many of the special geometric properties of these trees, see her Ph.D. thesis and other publications.
θ = 60°
θ = 108°
θ = 120°
θ = 144°
Among the results she has shown is how these trees relate to triangles, pentagons, and hexagons.
3 copies of 60° tree fit inside an equilateral triangle
If the three functions in the IFS for the self-contacting 45° symmetric binary tree are composed with the four elements of the Z_{4} cyclic symmetry group (rotations by 90°), the result will be a new iterated function system of 12 functions that exhibits Z_{4} symmetry (and in this case also reflective symmetry across horizontal, vertical, and diagonal lines through the center (D_{4} dihedral group symmetry) because of the symmetry of the base binary tree). In the image below, the random algorithm was used to draw 10 million points in the attractor for this IFS. The image was colored using pixel counting in which the colors represent how many times a particular pixel in the image was plotted (represented by the gradient on the right).
Mandelbrot, Benoit and Michael Frame. "The canopy and shortest path of a self-contacting fractal tree," The Mathematical Intelligencer, vol. 21, No. 2 (1999), 18-27.
Taylor, Tara. "A New Classification of Non-overlapping Symmetric Binary Fractal Trees Using Epsilon Hulls", Fractals, Vol. 17, No. 3 (2009), 365-384.
Taylor, Tara. "Excursions through a Forest of Golden Fractal Trees", in The Beauty of Fractals: 6 Different Views, eds. Denny Gulick and Jon Scott, Mathematical Association of America, 2010. [Excerpts available at Google Books]
West, Don. "Self-Contacting Fractal Trees, Comments on and Mathematical Details for an article by Mandelbrot and Frame." Website http://web.archive.org/web/20120313124012/http://faculty.plattsburgh.edu/don.west/trees/index.htm.
Field, Michael and Martin Golubitsky. Symmetry in Chaos: A Search for Pattern in Mathematics, Art, and Nature (2nd Edition), SIAM, 2009. [See Preview at Google Books. Chapter 7 is on Symmetric Fractals.]
Geom-e-tree by John Miller, Tree-Drawing App for iPad and iPhone. Can draw symmetric binary trees among many other possibilities.