Agnes Scott College
Larry Riddle, Agnes Scott College
image

The Shape of a Symmetric Binary Tree

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 Rk(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 Rk(LR) where k is the smallest integer with kθ ≥ 180°. But as observed by Don West (for the top of the tree) this may not always be the case as we examine below.

treedimensions
θ = 35°, r = 0.6
blue = right branch, red = left branch
top = 2.6539, side = 1.51964, bottom = 1.15588

Top of Tree

 
 
 

[Details]

(LR) Branch

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 Pn = T1T2T3...Tn where Ti 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.

topFourPaths
  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 limn->∞Pn 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 Rk. 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 Rk will actually be vertical. We now form the rest of the branches by alternating left and right. This yields the path Rk(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 rT such that if r > rT, then the top of the symmetric binary tree for that θ and r will correspond to the branch tip for Rk(LR), where k is the smallest integer for which kθ > 360°, rather than the branch tip for (LR). For example, if θ = 150°, then rT = 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

SBT-150-0.8twopaths2
θ = 150°, r = 0.8

The black path for R3(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.

Top of Tree
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.

Bottom of Tree

 
 
 
 
[Details]
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 Rk(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.

SCtopbottomgraph

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.

SCtreeheightgraph

 
  [Details]
As with the top of the tree, however, the branch tip for Rk(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 Rn(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 R2(LR) has a branch tip with y = 0.27365 while the blue path R4(LR) has a branch tip with y = 0.22498.

160-0.8 path
θ = 160°, r = 0.8
red: R2(LR)
blue: R4(LR)


Tree
Animation
Here is an image of that symmetric binary tree for θ = 160° and r = 0.8, along with the R4(LR) path.

SBT-160-0.8withpath
θ = 160°, r = 0.8

Side of Tree


 
 
[Details]
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 Rk(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 ≤ rsc. Moreover, in this case the bottom tip point will be for the path R2(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 < rsc = 0.61494, and the right tree has r > rsc but it also exhibits this behavior.

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

 
  [Details]
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 Rn(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 R5(LR) has a branch tip with x = 10.35548.

100-0.95-sidepaths
θ = 100°, r = 0.95
red: R(LR)
blue: R5(LR)

 
 

References

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