Larry Riddle, Agnes Scott College

θ = 35°, r = 0.6

blue = right branch, red = left branch

top = 2.6539, side = 1.51964, bottom = 1.15588

To get to the top of the tree, we want to go vertically as much as possible for each new branch in the construction of the tree. Thus we want to alternate left and right branches and follow the path (LR)^{∞}, or by symmetry the path (RL)^{∞}.
The branch tip for (LR)^{∞} is located at the point \((x,y)\) where
\[
x = \dfrac{-r \,\sin{(\theta)}}{1-r^2} \quad \text{ and } \quad
y = \dfrac{1+r\, \cos{(\theta)}}{1-r^2}.
\]

There are, in fact, many branch tips with the same y-coordinate as that for the (LR)^{∞} path, such as the branch tip for (RL)^{∞}, for example. Consider the finite path with address P_{n} = T_{1}T_{2}T_{3}...T_{n} where T_{i} is either the pair LR or the pair RL. Then the y-coordinate for the tip of the last branch of P will be the same as the y-coordinate for (LR)^{n}, as can be shown by induction on n. Here is an example of four different paths.

Blue: (LR)(LR)(LR)(LR)(LR)(LR)

Red: (LR)(RL)(LR)(RL)(RL)(LR)

Brown: (RL)(LR)(LR)(RL)(LR)(LR)

Purple: (RL)(RL)(RL)(LR)(LR)(RL)

If we now let n go to infinity, we see that the branch tip for the path lim_{n->∞}P_{n} will have the same y-coordinate as that for (LR)^{∞}. There are infinitely many such paths. This is why many symmetric binary trees appear to have a "flat" top as in the image above.

[Details]

But will (LR)^{∞} always be the path to the top of the tree? It turns out that the answer is "no".
Let k be the smallest integer such that kθ ≥ 360°. Consider the branch path that starts R^{k}. This path starts at the top of the trunk and goes clockwise until the last branch passes the upward vertical direction. If θ is of the form 360°/n, where n is an integer, then the last branch of R^{k} will actually be vertical. We now form the rest of the branches by alternating left and right. This yields the path R^{k}(LR)^{∞}. The y-coordinate of this branch tip is
\[ \sum_{n=0}^{k}{r^n \cos(n \theta)} + \frac{r^{k+1} \cos((k-1)\theta) + r^{k+2} \cos(k \theta)}{1-r^2}.
\]
For every angle θ that is **not** of the form 360°/n for some positive integer n, there is a value r_{T} such that if r > r_{T}, then the top of the symmetric binary tree for that θ and r will correspond to the branch tip for R^{k}(LR)^{∞}, where k is the smallest integer for which kθ > 360°, rather than the branch tip for (LR)^{∞}. For example, if θ = 150°, then r_{T} = 0.57735. Below is the symmetric binary tree for θ = 150° and r = 0.8, along with these two specific paths (here k = 3).

Branch

Animation

Tree

Animation

θ = 150°, r = 0.8

The black path for R^{3}(LR)^{∞} has a branch tip with y-coordinate 1.19607 while the green path for (LR)^{∞} leads to a branch tip with y-coordinate only at 0.85328 (the x-coordinates are 0.28262 and −1.11111, respectively). Notice that the branches of this tree have considerable overlap. This is particularly evident in the Tree Animation.

versus

Top of Trunk

We have been examining the top of a symmetric binary tree by looking at the branch tips. For 0° < θ ≤ 90°, the top branch tips are higher than the top of the trunk of the tree for all values of r. For 90° < θ < 180°, however, the y-coordinate of the (LR)^{∞} path will be greater than 1, the top of the trunk, only if
\[
\frac{1+r\cos(\theta)}{1-r^2} > 1 \quad \Rightarrow \quad r > -\cos(\theta) .
\]
This will happen for all self-contacting trees for θ ≤ 135°, but for θ > 135°, the top of the self-contacting tree will be below the top of the trunk of the tree. For larger choices of r, however, the top of the tree may still extend above the trunk, such as, for example, the tree shown above with θ = 150° and r = 0.8.

As with the top of the tree, we take the "bottom" of the tree to be the bottom branch tips, that is, the smallest y-coordinate of the branch tips. For most trees, the bottom of the tree will correspond to the y-coordinate of the branch tip of the path R^{k}(LR)^{∞}, where k is the smallest integer such that kθ ≥ 180°. We want a path that gets to the bottom as quickly as possible, so we take the path that bends right until it first crosses the downward vertical, then alternates left and right. The branch tip for this path will have y-coordinate given by
\[ \sum_{n=0}^{k}{r^n \cos(n \theta)} + \frac{r^{k+1} \cos((k-1)\theta) + r^{k+2} \cos(k \theta)}{1-r^2}.
\]
where k is the smallest integer such that kθ ≥ 180°.

The graphs below show the top (brown) and bottom (blue) values for the self-contacting trees as a function of θ. The "tallest" self-contacting tree occurs when θ = 45° and the top branch tip is at y = 2.19149. As θ approaches 180°, the top and bottom of the branch tips both converge towards 2/3.

We can take the "height" of the tree to be the difference between the top and bottom branch tips. Shown below is the graph of the height of the self-contacting trees as θ ranges between 0° and 180°. We see that the self-contacting trees grow in size until reaching a maximum height of 2 at θ = 90°, then begin to shrink except for a short growth spurt between 126.6° and 135°, after which they shrink down to a height of 0.

As with the top of the tree, however, the branch tip for R^{k}(LR)^{∞}, with k the smallest integer satisfying kθ ≥ 180°, will not always have the minimum y-coordinate. For some angles, if r is sufficiently large, then the path R^{n}(LR)^{∞}, where n is the smallest integer such that nθ ≥ 540°, may have a smaller y-coordinate. (Note that 540° = 180° + 360°, so this path takes another complete set of right turns until it again passes the downward vertical.) For example, this happens for θ=160° and r=0.8 as illustrated in the figure below (here k = 2 and n = 4). The red path R^{2}(LR)^{∞} has a branch tip with y = 0.27365 while the blue path R^{4}(LR)^{∞} has a branch tip with y = 0.22498.

θ = 160°, r = 0.8

red: R^{2}(LR)^{∞}

blue: R^{4}(LR)^{∞}

Tree

Animation

Here is an image of that symmetric binary tree for θ = 160° and r = 0.8, along with the R^{4}(LR)^{∞} path.

θ = 160°, r = 0.8

Now we want the branch tip that is farthest to the right. Let k be the smallest integer such that kθ ≥ 90°. The path we seek is R^{k}(LR)^{∞}. This path starts off bending to the right until it first passings a right angle from the initial vertical direction, then alternates left and right branches. The x-coordinate for the branch tip for this path will be
\[ \sum_{n=1}^{k}{r^n \sin(n \theta)} + \frac{r^{k+1} \sin((k-1)\theta) + r^{k+2} \sin(k \theta)}{1-r^2}.
\]
By the symmetry of the binary tree, the branch tip farthest to the left will be the negative of this value, and so the width of the tree will be twice this value.

Notice that if θ > 90°, then k = 1 and the path leading to the right side of the tree is R(LR)^{∞} = (RL)^{∞}, which is the same path whose branch tip is usually at the top of the tree. This will happen for all trees with θ > 90° and r ≤ r_{sc}. Moreover, in this case the bottom tip point will be for the path R^{2}(LR)^{∞} = R(RL)^{∞}. Thus the side and bottom tip points correspond to the "corner points" for the scaled subtree whose trunk is the first right branch. Below are two examples with θ = 110°. The left tree has r < r_{sc} = 0.61494, and the right tree has r > r_{sc} but it also exhibits this behavior.

θ = 110°, r =0.60 (self-avoiding) |
θ = 110°, r =0.71 (self-overlapping) |

As with the top and bottom, however, there are some combinations of angles and scaling factors for which the tree's side will extend past the branch tip described above. The path R^{n}(LR)^{∞}, where n is the smallest integer such that nθ ≥ 450°, may have a larger x-coordinate. (Note that 450° = 90° + 360°, so this path takes another complete set of right turns until it again passes the horizontal.) For example, this happens for θ=100° and r=0.95 as illustrated in the figure below (here k = 1 and n = 5). The red path R(LR)^{∞} has a branch tip with x = 9.59556 while the blue path R^{5}(LR)^{∞} has a branch tip with x = 10.35548.

θ = 100°, r = 0.95

red: R(LR)^{∞}

blue: R^{5}(LR)^{∞}

- Taylor, Tara.
*Computational Topology and Fractal Trees*, Ph.D. Thesis, Dalhousie University (2005).