Symmetric Binary Tree

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². 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.

The two branches are obtained from the trunk by scaling by a factor of r, rotating counterclockwise 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.

\({f_1}({\mathbf{x}}) = \left[ {\begin{array}{*{20}{c}} {r \cos (\theta )} & { - r\sin (\theta )} \\ {r\sin (\theta )} & {{{r \cos }}(\theta )} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{*{20}{c}} 0 \\ 1 \\ \end{array} } \right]\)	scale by r, rotate by θ°
\({f_2}({\mathbf{x}}) = \left[ {\begin{array}{*{20}{c}} {r \cos (\theta )} & { r\sin (\theta )} \\ {-r\sin (\theta )} & {{{r \cos }}(\theta )} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{*{20}{c}} 0 \\ 1 \\ \end{array} } \right]\)	scale by r, rotate by −θ°
\({f_3}({\bf{x}}) = \left[ {\begin{array}{*{20}{c}} { 1} & {0} \\ { 0} & { 1} \\ \end{array}} \right]{\bf{x}} \)

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.

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.

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°.

Self-avoiding r = 0.58 [Enlarge]	Self-contacting r = 0.61803 [Enlarge]	Self-overlapping r = 0.65 [Enlarge]

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.

 

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.

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	6 copes of 60° tree fit inside a hexagon	[Details]

 

5 copes of 108° tree fit inside a pentagon	5 copes of 108° tree fit inside a pentagram	[Details]

 

3 copes of 120° tree fit inside an equilateral triangle	5 copes of 120° tree fit inside a hexagon	[Details]

 

5 copes of 144° tree make a Golden Koch Snowflake		[Details]

Lévy Symmetric Binary Tree

The branch tips for a symmetric binary tree with θ = 45° and \(r = \frac{1}{\sqrt{2}}\) form a fractal that is the same as the Lévy Dragon.

Symmetric Binary Tree

Lévy Dragon

If four copies of a Lévy symmetric binary tree are placed at right angles, the branch tips will form the outside Lévy tapestry.

[Back Stitch Version, 12.5" x 12.5" on 18 count canvas]

If the three functions in the IFS for the self-contacting 45° symmetric binary tree are composed with the four elements of the Z₄ cyclic symmetry group (rotations by 90°), the result will be a new iterated function system of 12 functions that exhibits Z₄ symmetry (and in this case also reflective symmetry across horizontal, vertical, and diagonal lines through the center (D₄ 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).

[Enlarge]

 
 

1. Barnsley, Michael and D.P Hardin. "A Mandelbrot set whose boundary is piecewise smooth," Transactions of the American Mathematical Society, Vol. 315, No. 2 (1989), 641-658.
2. 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.
3. Mandelbrot, Benoit and Michael Frame. Geometry of Self-Contacting Binary Fractal Trees website.
4. Mendler, Nick and Vincent J. Matsko. "Symmetric Binary Trees with Branching Ratios Larger than 1," Proceedings of Bridges 2017: Mathematics, Art, Music, Architecture, Education, Culture, 507–510.
5. Pagon, Dusan. "Self-Similar Planar Fractals Based on Branching Trees and Bushes," Progress of Theoretical Physics Supplement, No. 150, 176-187.
6. Pons, Bernat Espigulé. Unfolding Symmetric Fractal Trees, Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture, Edited by George Hart and Reza Sarhangi, pp295-302.
7. Pons, Bernat Espigulé. Adventures into the Mathematical Forest of Fractal Trees, Wolfram Blog, May 22, 2014.
8. Taylor, Tara. Computational Topology and Fractal Trees, Ph.D. Thesis, Dalhousie University (2005).
9. Taylor, Tara. "Finding Gold in the Forest: Self-contacting Symmetric Binary Fractal Trees and the Golden Ratio".
10. Taylor, Tara. "Golden Fractal Trees," Bridges Donostia: Mathematics, Music, Art, Architecture, Culture (2007), 181–188 .
11. Taylor, Tara. "A New Classification of Non-overlapping Symmetric Binary Fractal Trees Using Epsilon Hulls", Fractals, Vol. 17, No. 3 (2009), 365-384.
12. 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]
13. 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.
14. 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.]
15. Geom-e-tree by John Miller, Tree-Drawing App for iPad and iPhone. Can draw symmetric binary trees among many other possibilities.