PATH LENGTH AND HEIGHT IN ASYMMETRIC BINARY BRANCHING TREES

Amelia O’Hanlon, Patricia Howard, and David A. Brown

Abstract This work is inspired by a paper by Mandelbrot and Frame [1], in which they describe properties of symmetric binary branching trees. We study a variation of their trees in which non–uniform scaling is applied, focusing on geometric properties such as path length and tree height. We also discuss the computer implementation via Mathematica.

1. Introduction. We study the geometry of asymmetric binary branching trees, a variation on the symmetric trees found in [1], focusing on path length and tree height. Instead of using a uniform scaling ratio in the branching process, we chose to apply different scalings based upon whether branching occurred to the left or to the right. These trees will be referred to as asymmetric branching binary trees, or simply asymmetric trees. This slight change leads to a wealth of new geometric characteristics.

In order to better understand asymmetric trees it is first necessary to consider their symmetric counterpart. To construct a symmetric branching tree, first construct a vertical segment which will be referred to as the trunk. For simplicity let the trunk have unit length. Then extend two branches from the tip of the trunk, each branching by an angle θ > 0^{∘} from the vertical extension of the trunk and having length r, where r ∈ (0, 1) is a scaling ratio. Two branches are then created from the tips of each of these branches in a similar fashion. At this stage, the four new branches will have length r^{2}. This process is continued indefinitely [see Figure 1A]. Notice that the length of branches created at stage n is r times the length of the branches at stage n − 1.

Asymmetric trees, constructed in a similar manner, will use two scaling ratios [see Figure 1B]. Let r_{1} be the scaling ratio applied to right branchings and r_{2} be the scaling ratio applied to left branchings. Also, we assume that 0 < r_{2} < r_{1} < 1. The angle at which each branch is rotated from the extension of the previous branch (or trunk) will remain constant throughout the tree. By altering a symmetric tree in this way we lose left–right symmetry.

In a fractal tree, every branch can be described using a finite number of left turns and right turns. For example, the branch at the address T LR is found by traveling along the trunk, taking a left turn at the first branching and then taking a right turn at the second branching. Similarly, a path within the tree can be described by the left turns and right turns contained in it. For example, an infinite path of alternating right and left turns has the address T RLRL ⋯ = T (RL)^{∞} and a finite path contained in that path is T RLRL.

In Section 2, we analyze the lengths of infinite paths emanating from the base of the trunk of the tree. The lengths of infinite paths can be determined by summing an appropriate series. In symmetric trees, this is the geometric series 1 + r + r^{2} + ⋯ = \frac{1}{1−r}. Because all the branches constructed at the same stage have the same length, every infinite path beginning at the base of the trunk in a symmetric tree will have the same length, \frac{1}{1−r}. In contrast to the study of path lengths in the symmetric trees, asymmetric trees introduce complications due to the non–uniform scaling. Clearly, T R^{∞} is the longest path, having length |T R^{∞}| = \frac{1}{1−r_{1}} , while T L^{∞} is the shortest path, with length \frac{1}{1−r_{2}} .

In Section 3, we give an analysis of tree height for asymmetric trees. If the tree is placed on the Cartesian plane with the trunk lying on the y–axis and the base at the origin, then the height is defined to be the largest y–coordinate in the tree. Although every path in a symmetric tree has the same length, they do not all reach the same height. For example, the path T R^{∞} in Figure 1A clearly does not reach the greatest height. Now, consider branches T RR and T RL. Notice that it is always the vertical branch that reaches the greater height. Therefore, by constructing a path with as many vertical branches as possible, e.g. T (RL)^{∞} or T (LR)^{∞}, the greatest height can be obtained. So the total height of the tree, i.e. the height of the path T (RL)^{∞} or T (LR)^{∞}, can be found using the equation

1 + r cos(θ) + r^{2} + r^{3} cos(θ) + r^{4} + ⋯ = \frac{1 + r cos(θ)}{1 − r^{2}}.

The paths T (RL)^{∞} and T (LR)^{∞} are also significant because they are examples of opposite paths [see Figure 2]. In order to determine the address for a path’s opposite, switch the positions of the R’s and L’s in the address. T (RL)^{∞} is also an example of a periodic path, meaning the address consists of T followed by the pattern RL repeated infinitely.

Another term that will be important later is corresponding branches. Consider that the branches T R and T L can be thought of as trunks of scaled down trees. Branches in the analogous positions in these trees are corresponding branches, as shown with branches f and g in Figure 2. Similarly, f corresponds to both branches h and i in different scaled down trees.

In Section 4, we discuss the use of Mathematica in drawing and analyzing asymmetric trees. We also outline how to use the package created for this study.

Finally, in Section 5, we provide some conjectures and questions for further study. In particular, we discuss space–filling curves.

2. Path Length. Given an asymmetric tree, we can study the length, |P |, of a path P. Using geometric series, equations for infinite periodic path lengths are

\begin{aligned}|T (R^{m}L^{n})^{∞}| & = \frac{\frac{1−r_{1}^{m+1}}{1−r_{1}} + \frac{r_{1}^{m}r_{2}(1−r_{2}^{n−1})}{1−r_{2}}}{1 − r_{1}^{m}r_{2}^{n}} , \\ |T (L^{m}R^{n})^{∞}| & = \frac{\frac{1−r_{2}^{m+1}}{1−r_{2}} + \frac{r_{2}^{m}r_{1}(1−r_{1}^{n−1})}{1−r_{1}}}{1 − r_{2}^{m}r_{1}^{n}} , \end{aligned}

where 0 < r_{2} < r_{1} < 1 and m, n ∈ ℕ ∪ {0} and m and n cannot both be 0. It is important to note that the second equation can be derived from the first by simply switching r_{1} and r_{2} since these paths are opposite [see Figure 2]. Other opposite paths exist, but their lengths cannot be defined with the above equations (e.g. T RL^{∞} and T LR^{∞}).

One of the topics that will appear repeatedly is symmetry. Although these trees have an asymmetric branching pattern, they are still self–similar. Every branch can be thought of as the trunk of a scaled down tree, lending to many interesting characteristics in an asymmetric tree.

In particular, self–similarity permits us to study path lengths. By setting the formulas for |T RL^{∞}| and |T LR^{∞}| equal to each other, we can find a relationship between r_{1} and r_{2} in which these opposite paths are equal in length:

|T RL^{∞}| = |T LR^{∞}| ⟹ 1 + r_{1}(\frac{1}{1 − r_{2}} ) = 1 + r_{2}(\frac{1}{1 − r_{1}} )

⟹ r_{2}(1 − r_{2}) = r_{1}(1 − r_{1})
⟹ r_{1}^{2} − r_{1} + (r_{2} − r_{2}^{2}) = 0.

Solving for r_{1}, we find that

r_{1} = 1 − r_{2} or r_{1} = r_{2}.

Thus, |T RL^{∞}| and |T LR^{∞}| are equal if r_{1} + r_{2} = 1 or r_{1} = r_{2}. The latter is the case of a symmetric branching tree, which we do not consider.

Self–similarity in fractal trees implies that if a characteristic can be defined for the whole tree, that some characteristic can be found in each smaller tree within it. So, when r_{1} + r_{2} = 1 there are infinitely many pairs of paths equal in length stemming from the trunk. Each pair in this infinite set of equal path lengths corresponds to the pair (T RL^{∞}, T LR^{∞}) and every other pair in the set. Three corresponding pairs are highlighted in Figure 3.

Other sets of pairs of equal length opposite paths are found by setting the formulas for |T R^{n}L^{∞}| and |T L^{n}R^{∞}| equal to each other. These paths are equal in length if r_{1} = (1 − r_{2}^{n})^{1/n} or r_{1} = r_{2}.

Using generalized formulas for |T (R^{m}L^{n})^{∞}| and |T (L^{m}R^{n})^{∞}|, we found a significant restriction on whether a pair of periodic opposite paths can be equal.

\underline{Theorem 2.1}. If m ≥ n, where m ≥ 1, n ≥ 0, then |T (R^{m}L^{n})^{∞}| > |T (L^{m}R^{n})^{∞}|.

\underline{Proof}. For m ≥ 1, n ≥ 0, we find that

|T (R^{m}L^{n})^{∞}| = \frac{\frac{1−r_{1}^{m+1}}{1−r_{1}} + \frac{r_{1}^{m}r_{2}(1−r_{2}^{n−1})}{1−r_{2}}}{1 − r_{1}^{m}r_{2}^{n}}

and

|T (L^{m}R^{n})^{∞}| = \frac{\frac{1−r_{2}^{m+1}}{1−r_{2}} + \frac{r_{2}^{m}r_{1}(1−r_{1}^{n−1})}{1−r_{1}}}{1 − r_{2}^{m}r_{1}^{n}} .

Now, since 0 < r_{2} < r_{1} < 1 it follows that r_{1}^{p} > r_{2}^{p} and r_{1}^{p}r_{2}^{q} ≥ r_{2}^{p}r_{1}^{q} for all p, q ∈ ℤ with p ≥ q. Thus,

∑_{j=0}^{m} r_{1}^{j} + ∑_{k=1}^{n−1} r_{1}^{m}r_{2}^{k} > ∑_{j=0}^{m} r_{2}^{j} + ∑_{k=1}^{n−1} r_{2}^{m}r_{1}^{k}

which implies that

(\frac{1 − r_{1}^{m+1}}{1 − r_{1}} ) + (\frac{r_{1}^{m}r_{2}(1 − r_{2}^{n−1})}{1 − r_{2}}) > (\frac{1 − r_{2}^{m+1}}{1 − r_{2}} ) + (\frac{r_{2}^{m}r_{1}(1 − r_{1}^{n−1})}{1 − r_{1}}).

Since 1 − r_{1}^{m}r_{2}^{n} < 1 − r_{2}^{m}r_{1}^{n}, we find

\frac{(\frac{1−r_{1}^{m+1}}{1−r_{1}} ) + (\frac{r_{1}^{m}r_{2}(1−r_{2}^{n−1})}{1−r_{2}})}{1 − r_{1}^{m}r_{2}^{n}} > \frac{(\frac{1−r_{2}^{m+1}}{1−r_{2}} ) + (\frac{r_{2}^{m}r_{1}(1−r_{1}^{n−1})}{1−r_{1}})}{1 − r_{2}^{m}r_{1}^{n}}.

Therefore, |T (R^{m}L^{n})^{∞}| > |T (L^{m}R^{n})^{∞}|.

To continue our study of paths of equal length we had to resort to Mathematica. Finding values for r_{1} and r_{2} in which a pair of opposite paths were equal required an enormous number of calculations and the evaluation became too cumbersome. Studying path lengths that cannot be defined with our equations for |T (R^{m}L^{n})^{∞}| and |T (L^{m}R^{n})^{∞}| may require a different approach.

3. Tree Height. Tree height is defined by the largest y–coordinate in the path that has the most vertical reach. When θ > 90^{∘} the trunk can be taller than its branches, which could possibly change the analysis of tree height as discussed here. θ < 0^{∘} is essentially a reflection across an extension of the trunk. We limited our tree height study to trees in which 0^{∘} < θ ≤ 90^{∘}. Thus, the question is: which path do we use to determine tree height? We know that the first right branch always has a greater vertical reach than the first left branch. Likewise, the right side of the tree is taller than the left side.

The path which determines tree height is found by comparing the height of the path T R^{n} to that of T R^{n−1}L for n ≥ 2 (for n = 1, height(T R) will always be greater than height(T L)). Note that height (P) denotes the largest y–coordinate of the path P. This method of determining which path defines tree height is necessary since the height(T R^{n−1}L) is not always greater than height(T R^{n}) [see Figure 4].

The four quantities that determine whether a right branch extends above the left branch stemming from the same previous branch (or trunk) are θ, n, r_{1}, and r_{2}. If θ = 90^{∘}, then two of the paths determining tree height are T (RL)^{∞} and T (LR)^{∞}, the same as for symmetric trees. For 0^{∘} < θ < 90^{∘}, the tip of a right branch can have a greater height than the tip of the left branch stemming from the same previous branch. Whether this occurs or not depends on the values for n and the ratio \frac{r_{1}}{r_{2}} .

Using trigonometry, we compare the heights of any two paths, resulting in the correct inequalities to test. In particular, the y–coordinates of branches can be determined using trigonometry, as Figure 4 illustrates. We can now find an inequality in terms of n that determines if the n^{th} branch exhibiting greater height is a left or right branch

height(T R^{n−1}L) ≥ height(T R^{n})
⟺ r_{1}^{n−1}r_{2} cos((n − 2)θ) ≥ r_{1}^{n} cos(nθ)
⟺  r_{2} cos((n − 2)θ) ≥ r_{1} cos(nθ)

⟺  \frac{r_{2}}{r_{1}} ≥ \frac{cos nθ}{cos(n − 2)θ} .

Thus, when the last inequality above is true, the height of the left branch attached to the (n − 1)^{th} right branch is greater than, or equal to, the height of the n^{th} right branch. If the left and right branches at the (n − 1)^{th} branching are equal in height, then either branch determines tree height.

Once it has been determined that turning left on a path to greatest tree height is preferred to turning right, then the path of greatest height can be determined without further examination of the branches in the sequence. This results from similar triangles constructed at the n^{th} and (n − 2)^{th} branchings.

If T R^{3}L reaches greater height than T R^{4} [see Figure 5], then the next comparison that would be made to determine tree height is height(T R^{3}L^{2}) ≥ height(T R^{3}LR). The angles in the previous triangles used to find the last terms in the equations for height(T R^{2}L) and height(T R^{3}) are congruent to the angles in the triangles we would use for height(T R^{3}L^{2}) and height(T R^{3}LR). Thus, if a right branch was chosen the first time these triangles were used in a comparison, then a right branch would be chosen again. This also means that any time a left branch is chosen, the path determining height is the one alternating from that point onward (e.g. T R^{n−1}(LR^{∞}).

Up to this point we have made the assumption that there exists a positive integer n for which r_{2} cos((n − 2)θ) ≥ r_{1} cos(nθ) is true but it is not necessarily clear that this is always the case. The following theorem will clarify this and provide an expression for n as a function of r_{1}, r_{2} and θ.

\underline{Theorem 3.1}. Suppose that 0 < r_{2} < r_{1} < 1 and 0 < θ ≤ \frac{π}{2} . Then, there exists n ≥ 2 such that r_{2} cos((n − 2)θ) ≥ r_{1} cos(nθ).

\underline{Proof}. Using trigonometric identities, the inequality r_{2} cos((n − 2)θ) ≥ r_{1} cos(nθ) can be rewritten in the form

r_{2} cos((n − 2)θ) ≥ r_{1}(cos 2θ cos((n − 2)θ)
− sin 2θ sin((n − 2)θ))
⟺ r_{2} cos((n − 2)θ) − r_{1} cos 2θ cos((n − 2)θ) ≥ −r_{1} sin 2θ sin((n − 2)θ)
⟺  cos((n − 2)θ)(r_{2} − r_{1} cos 2θ) ≥ −r_{1} sin 2θ sin((n − 2)θ)
⟺  r_{1} sin 2θ sin((n − 2)θ) ≥ − cos((n − 2)θ)(r_{2} − r_{1} cos 2θ)

⟺  \frac{sin((n − 2)θ)}{cos((n − 2)θ)} ≥ \frac{r_{1} cos 2θ − r_{2}}{r_{1} sin 2θ}

⟺  tan((n − 2)θ) ≥ cos 2θ − \frac{r_{2}}{r_{1}} csc 2θ.

Since cot 2θ − \frac{r_{2}}{r_{1}} csc 2θ is constant and tan(x) is an increasing function, there is a smallest integer n such that tan((n − 2)θ) ≥ cot 2θ − \frac{r_{2}}{r_{1}} csc 2θ.

Now, we can write n as a function of r_{1}, r_{2}, and θ

n(r_{1}, r_{2}, θ) = smallest integer greater than (\frac{arctan(cot 2θ − \frac{r_{2}}{r_{1}} csc 2θ}{θ} + 2).

By using geometric series and summing all the terms for the heights of each right branch up to (and not including) the n^{th} branching, we get the following formula for tree height

∑_{j=0}^{n−1}(r_{1}^{j} cos(jθ)) + \frac{r_{1}^{n−1}r_{2} cos((n − 2)θ) + r_{1}^{n}r_{2} cos((n − 1)θ)}{1 − r_{1}r_{2}}.  (3.1)

If at the (n − 1)^{th} branch the left and right branches are equal in height, then more than one path determines tree height. From the first comparison in which the left and right branches were equal in height we know there must be at least two paths for tree height. Again, due to similar triangles, the height of the right and left branches will be equal at alternate branchings. Thus, if there is more than one path determining tree height, there are infinitely many paths determining tree height [see Figure 6].

4. Computer Implementation. To generate pictures of fractal trees, affine transformations are necessary. The two functions for generating symmetric trees are as follows:

S_{L}(x, y) = (rx cos(θ) − ry sin(θ), rx sin(θ) + ry cos(θ) + 1)
S_{R}(x, y) = (rx cos(−θ) − ry sin(−θ), rx sin(−θ) + ry cos(−θ) + 1).

Since asymmetric trees have three variables involved in their construction it is quite difficult to visualize how minor changes in these variables may affect the characteristics in the tree. For this reason, it is important to have a means of producing accurate pictures of these trees. These transformations are:

A_{L}(x, y) = (r_{2}x cos(θ) − r_{2}y sin(θ), r_{2}x sin(θ) + r_{2}y cos(θ) + 1)

A_{R}(x, y) = (r_{1}x cos(−θ) − r_{1}y sin(−θ), r_{1}x sin(−θ) + r_{1}y cos(−θ) + 1).

We wrote a Mathematica package to implement the iteration of these affine transformations and to generate the figures in this paper. This package is available upon request from the third author.

5. Further Investigations. There are many other topics concerning asymmetric branching trees that we have yet to study. One of the main topics that Mandelbrot and Frame [1] address is self–contact in symmetric trees. In particular they discussed trees with θ = 135^{∘} and θ = 90^{∘}. At θ = 135^{∘} the tree fills a right isosceles triangle [see Figure 7] and at θ = 90^{∘} the tree fills a rectangle [see Figure 8] with certain values of r. One of the characteristics of asymmetric trees that computer generated pictures allowed us to see was that these trees no longer completely fill regular polygons. Furthermore, there will always be a gap in the lower left corner of the rectangle and on the left side of the trunk in the triangle, since r_{1} > r_{2}. In the future, we plan to measure this gap in terms of r_{1}, r_{2}, and θ. These two examples lead to the world of space–filling curves and open up other avenues of study.

Figure 1. Comparison of symmetric and asymmetric branching trees. Both have θ = \frac{π}{10}. A has r = \frac{1}{2}, and B has r_{1} = \frac{1}{2}, r_{2} = \frac{1}{4}.

Figure 2. Opposite paths T (RL)^{∞} and T (LR)^{∞}, and some corresponding branches. 10 Figure 3. Pairs of equal length paths: (T RL^{∞}, T LR^{∞}), (T R^{2}LR^{∞}, T R^{3}L^{∞}),

and (T R^{2}RL^{∞}, T L^{3}R^{∞}). Here, r_{1} = \frac{3}{4}, r_{2} = \frac{1}{4}, θ = \frac{π}{3} .

Figure 4. Part of an asymetric tree with r_{1} = \frac{3}{4}, r_{2} = \frac{1}{4}, θ = \frac{π}{10}.

12 Figure 5. Tree height analysis where r_{1} = \frac{18}{20}, r_{2} = \frac{5}{20}, θ = \frac{π}{9} .

13 Figure 6. Multiple paths determine tree height. Here, r_{1} = \frac{3}{4}, r_{2} = \frac{3}{8}, θ = \frac{π}{6} .

14 Figure 7. Trees that are space–filling curves. On the left, the symmetric tree fills

a triangle. The asymmetric tree does not quite fill a triangle. Both trees have θ = 135^{∘}.

Figure 8. On the left is a symmetric tree with r = (1/\sqrt{2}). On the right is an asymmetric tree with r_{1} = (1/\sqrt{2}) + 1/18 and r_{2} = (1/\sqrt{2}). Both trees are space–filling curves and have θ = π/2.

\underline{Reference}

1. B. Mandelbrot and M. Frame, “The Canopy and Shortest Path in a Self– Contacting Fractal Tree,” Math Intelligencer, 21 (1999), 2.

Amelia O’Hanlon Department of Mathematics and Computer Science Ithaca College Ithaca, NY 14850 email: aohanlo1@ic3.ithaca.edu

Patricia Howard Department of Mathematics and Computer Science Ithaca College Ithaca, NY 14850 email: phoward1@ic3.ithaca.edu

David Brown Department of Mathematics and Computer Science Ithaca College Ithaca, NY 14850–7284 email: dabrown@ithaca.edu