Finding Fibonacci In Golden Trees
Tags: datastructures, mathematics, computerscience, theoryinpractice
Published: 2018-02-10 22:35:30

---
title: "Finding Fibonacci In Golden Trees"
published: true
tags: data-structures,mathematics,computer-science,theory-in-practice
canonical_url: https://medium.com/basecs/finding-fibonacci-in-golden-trees-1c8967b1f47a
---

![](https://cdn-images-1.medium.com/max/1024/1*TWkFGCTF_Nn3I0CVCJDrkg.jpeg)<figcaption>Finding Fibonacci in golden (AVL)Â trees</figcaption>

Learning new things always brings the opportunity to have your mind completely blown. Mind you, this always doesn’t happenâ€Š–â€Šat least when it comes to the realm of computer science. However, every once in awhile, you learn something that truly awes you, something that is actually _awesome_ in the actual dictionary definition sense of the word; something that really feels like a lightbulb going off, making you feel very grateful to have set about trying to understand it in the first&nbsp;place.

I’m speaking from personal experience, of course, because this was exactly what happened to me when I learned about the wonders of AVL trees. It turns out that computer science has elements of mathematics under the surface, some of which we have already seen in the course of this series. But mathematics also has another hidden layer to it, as well: a connection to the natural world around&nbsp;us.

Oftentimes, when we learn about super theoretical stuff (like a lot of core computer science concepts) it’s hard to connect the dots between where these concepts were created, why we use them, and why we should care. Understanding the history of why something was invented is just as important as comprehending its applications and usage. It’s a bit rare for us to be able to see how something in computer science directly connects to other fields that have nothing to do with computing!

In today’s post, however, mathetmatics, computer science, and nature all come together in the most magical of ways. So, let’s get to&nbsp;it!

### Looking for tree&nbsp;patterns

Last week, we learned about a unique data structure called [an AVL tree](https://dev.to/vaidehijoshi/the-little-avl-tree-that-could), which is a type of self-balancing binary search tree. Hopefully you remember that an AVL tree is a height-balanced tree, which means that it follows a golden rule: no single leaf in the tree should have a significantly longer path from the root node than any other leaf on the&nbsp;tree.

The important thing to keep in mind about this golden rule is that as an AVL tree grows in height, it must have a minimum number of nodes at each level before another one can be&nbsp;added.

![](https://cdn-images-1.medium.com/max/1024/1*xvei9W5JUdbhBe_P83luDQ.jpeg)<figcaption>The heights of AVL trees and the minimum number of nodes to createÂ them.</figcaption>

The illustration shown here exemplifies this. In this drawing, we can see five different AVL trees, each with a varying&nbsp;heights.

In the AVL tree with a height of 0, there are no nodes, so _n_ is equal to 0. In the AVL tree with a height of 1, there is exactly 1 node, while in an AVL tree with a height of 2, there are exactly 2 nodes. Remember, we’re only considering the minimium number of nodes. Technically, we could have added a third node to our AVL tree with a height of 2, and that would still be fine; but, we need at _least_ two nodes in order to create a height-balanced AVL tree with a height of&nbsp;2.

What happens when we need to create an AVL tree with a height of 3? Well, we need 4 nodes at minimum to do that, since we need to add a right subtree before we can go about adding another level. It’s a similar situation for the tree with a height of 4: we need 7 nodes in order to create a height-balanced right subtree before adding another node to the left&nbsp;subtree.

Let’s take it one step further: what is the minimum number of nodes that we need in order to create an AVL tree with a height of&nbsp;5?

![](https://cdn-images-1.medium.com/max/1024/1*chwidRilzVydjz1BwszJ-w.jpeg)<figcaption>The minimum number of nodes for an AVL tree with a height ofÂ 5.</figcaption>

Well, based on [what we learned](https://dev.to/vaidehijoshi/the-little-avl-tree-that-could) last week about AVL trees, we know that the difference between the left and the right subtrees cannot be more than one level in height. This means that we’ll need to add to our right subtree before we can grow our left&nbsp;subtree.

The example shown here illustrates what our minimum-node number for an AVL tree with a height of 5 would be: we need, at a minimium, 12 nodes in order to create an AVL tree with a height of 5. If we break this down further, we can see that we need 7 of those nodes in the left subtree, and 4 nodes for the right subtree. And, of course, we need a node for the&nbsp;root.

If we look at the left subtree and the right subtree for long enough, we’ll notice that they seem familiar. That’s because we just saw them a minute ago when we were looking at our AVL trees with a height of 4 and 3! Those two trees just happen to be the two structures that came before the AVL tree with a minimum node count and a height of&nbsp;5.

If you feel like there’s an interesting pattern here, you’re be&nbsp;right.

> The height of an AVL tree with the minimum number of nodes is a combination of the two minimum-height AVL trees preceding it.

This is not unique to the AVL tree with a height of 5; in fact, if we look back at the earlier illustration and close closely at the AVL tree with a height of 4, we’ll notice the exact same pattern. The left subtree of the an AVL tree with a height of 4 is the AVL tree with a height of 3, while the right subtree is the the AVL tree with a height of&nbsp;2.

We could even continue to draw larger height-balanced trees and see this pattern continue, even as the height of a tree gets immensely large.

So, how can transform this pattern out into something more abstract? We derive this pattern to the following formula: “_the height of a tree_ _n is equivalent to the sum of the heights of trees_ _n-1 plus_ _n-2 plus&nbsp;__1”_.

![](https://cdn-images-1.medium.com/max/1024/1*Pc5MCwYKzR94QyEi8Y4bxg.jpeg)<figcaption>The forumla for figuring out the height of a fibonacci tree</figcaption>

Another way to think about this is that the minimum number of nodes to create a tree of height _n_ is by combining the two trees that come before it, and adding another node for the root node. In other words, in order to determine the minimum number of nodes necessary to create a tree with a height of 10, you’d need the number of nodes from the tree with a height of 9 and with a height of 8, plus one additional node for the root&nbsp;node.

If we sum the two AVL trees before the one we’re looking for, we can programmatically figure out the minimum number of nodes we’ll need to create any given height-balanced AVL&nbsp;tree.

VoilÃ ! We’ve discovered the Fibonacci sequence right under our&nbsp;noses!

### Finding Fibonacci and the golden&nbsp;ratio

The pattern of “summing two numbers to get the third number is known as the Fibonacci sequence, named after [Leonardo Fibonacci](https://math.temple.edu/~reich/Fib/fibo.html). What young Leonardo stumbled upon could be summarized as a mathematical sequence that follows a single rule, which is exactly what we know to be the Fibonacci sequence:

> every number after the first two numbers is the sum of the two numbers that preceded&nbsp;it.

Once we have the first two numbers of the Fibonacci sequence, we have enough to build the entire thing (but it goes on forever and forever, so we’ll just skip that for now)! And it just so happens that the first two numbers are pretty easy to remember: they’re 0 and&nbsp;1.

![](https://cdn-images-1.medium.com/max/1024/1*KQD6UCzG_EHOE1_FM8BuKA.jpeg)<figcaption>The Fibonacci sequence</figcaption>

We already know that there’s some kind of correlation between the Fibonacci sequence and the left and right subtree of a height-balanced AVL tree. Namely, we know that the minimum number of nodes for a tree with a height of _H_ will be the two minimum node trees that come before it, plus one more node for the root&nbsp;node.

Since we derived a formula in the previous section to determine the _height_ of the tree based on the number of nodes, can we use the Fibonacci sequence to determine the reverse? Can we abstract out a formula to determine the minimum number of nodes for a tree based on it’s&nbsp;height?

Of course we&nbsp;can!

Let’s break down the math that’s working behind the scenes here and see if we can figure out what’s actually going&nbsp;on.

In the illustration shown here, we’re going to do the reverse of the formula we deduced earlier, which means that we’ll continue working with a tree with a height _H_ of 5. If we’re looking for _n_, the minimum number of nodes for a tree of height _H_, we can find the Fibonacci number located at the index of Fibonacci[H+2], and subtract one from it in order to determine the minimum number of nodes to create a tree of height&nbsp;_H_.

![](https://cdn-images-1.medium.com/max/1024/1*YQ3YX5HznVRtCaO9ENOPkQ.jpeg)<figcaption>The formula to determine the minimum number of nodes for a tree of heightÂ H.</figcaption>

So, in the case of a tree with a height _H_ of 5, we’ll need to find the Fibonacci number at the index of 5 + 2, or 7. Recall that we indexed our Fibonacci sequence beginning with 0 as the first index, so the element at Fibonacci[7] will give us 13. Since 13 - 1 is 12, we know that we’ll need a minimum of 12 nodes to create a tree with a height of&nbsp;5.

When we drew out a balanced tree with a height of 5 in the previous section, that’s exactly how many nodes we&nbsp;had!

Okay, what about a tree with a height _H_ of 6? Well, 6 + 2 is 8, and the element located at the index of Fibonacci[8] would be the number 21. Remember, even if we don’t know the element at the index of Fibonacci[8], we know that Fibonacci[6] = 8 and Fibonacci[7] = 13, which means we can sum these two in order to get the next element in the sequence. Since Fibonacci[8] = 21, we can subtract one from it and know that we need, at a minimum, 20 nodes in order to create a height-balanced AVL tree with a height of&nbsp;6.

Rad! We just reversed our first formula, which used the Fibonacci pattern, into its opposite…which _also_ uses the Fibonacci pattern!

Okay, that’s pretty cool, but it’s about to get even&nbsp;cooler.

The sequence that has long been attributed to (and named for!) Fibonacci was actually discovered hundreds of years earlier by [ancient Indian mathematicians](http://www.storyofmathematics.com/medieval_fibonacci.html), way back in the 6th century. It was only with Fibonacci’s discovery of it 600 years later that the western world came to know of this sequence, and were thus able to study it in even greater&nbsp;depth.

As more mathematicians, scientists, and artists started studying this sequence, they began to understand its deep connections to the world around us. One of the things that they discovered was that the Fibonacci sequence was very closely linked to another special property in geometry and mathematics: the golden spiral and the golden&nbsp;ratio.

It’s unclear when the **_golden ratio_** was discovered; although it was Greek mathematician Euclid who first mentioned it in his famous, well-studied and well-cited text, “_Elements_”, it’s also very possible that the ancient Egyptians used it when they [built the pyramids](https://www.goldennumber.net/golden-ratio-history/), thousands of years ago. The golden ratio is often referred to as “_phi_ (_Ï†_ or _Ï•_), and is also known as DaVinci’s “_golden proportion”_. In mathematical terms, two quantities have a golden ratio if the ratio between the two quantities is the same as the ratio of the two elements summed when compared to the larger of the two quantities.

The golden ratio is usually illustrated by using the example of a rectangle made up of a square and a rectangle, respectively.

![](https://cdn-images-1.medium.com/max/1024/1*dcynt8UQnFdPy3fUt7H-xg.jpeg)<figcaption>The golden ratio: a definition</figcaption>

In the example shown above, we can see the golden ratio at work. When we divide a line into two parts such that the whole length divided by the larger part is equal to the larger part divided by the smaller part, we end up with the golden ratio. In this particular illustration, the ratio of the longer side of the rectangle, the sum of _a + b_, to the side _a_ will be the same as the ratio of the length of _a_ to the side&nbsp;_b_.

But what exactly _is_ the golden ratio? We’re comparing _a_’s and _b_’s, but what does that mean, really? Well, let’s look at the golden ratio using actual numbers, and see if we can get to a more concrete&nbsp;answer.

We know that the golden ratio is often described as&nbsp;follows:

> a + b is to a, as a is to&nbsp;b

Let’s replace _a_ and _b_ here with integers: a = 5 and b =&nbsp;3.

![](https://cdn-images-1.medium.com/max/1024/1*VGNJRzc0C5XMGAE75VCDIA.jpeg)<figcaption>The golden ratio is also known as Ï† orÂ <em>Ï•.</em></figcaption>

If _a + b is to a, as a is to b_, then we should be able to prove that 5 + 3 to 5 has the same ratio as 5 does to&nbsp;3.

Well, it’s time to do the math and find out if that’s really the&nbsp;case!

Since 5 + 3 = 8, we determine the ratio here by dividing 8/3, which is 1.6. If we divide 5/3, we get 1.6, repeating.

In both of these instances, we’re actually coming very close to the value of _phi (Ï†)_, which is an irrational number that is the sum of 1 and the square root of 5, divided by 2. This irrational number roughly _approximates_ to 1.6180339887, often just referred to as 1.618, for&nbsp;short.

So how does the golden _ratio_ tie into the golden _spiral_? Well, the **_golden spiral_** is a geometric, logarithmic spiral whose growth factor actually happens to beâ€Š–â€Šsurprise, surprise!â€Š–â€Šthe golden ratio. And guess what? The Fibonacci sequence comes into play here again,&nbsp;too!

If we construct squares with the width of each consecutive element in the Fibonacci sequence, we can start to build up rectangles. We’ll notice that each one of these rectangles has the _golden ratio_ within it! And, as these rectangles grow, a spiral shape begins to&nbsp;emerge.

![](https://cdn-images-1.medium.com/max/1024/1*KMsWsDm2cKAwrQL8oWiWGQ.jpeg)<figcaption>The Golden Spiral as a manifestation of the Fibonacci sequence.</figcaption>

We’ll notice that each square’s width is made up of two parts: another square and a rectangle, each of whose widths are the sums of the two squares (the two Fibonacci numbers) that precede it. For example, the width of the square 8, drawn in pink, is the sum of the widths of the two squares that came before it: 5 and 3. Similarly, the width of the red square 13 is the sum of the two squares that came before it: 8 and&nbsp;5.

The Fibonacci sequence appears once again! The ratio between each of these squares that we used to build up our golden spiral is tied directly to the golden ratio. If we divide each Fibonacci number by the number that preceded it, this becomes more&nbsp;obvious.

![](https://cdn-images-1.medium.com/max/1024/1*b9ub0f4jSFjOGhPjtN4N9w.jpeg)<figcaption>The larger the Fibonacci number, the closer we get to the goldenÂ ratio.</figcaption>

Notice that we get closer and closer to the actual value of _phi (Ï†)_ as our Fibonacci numbers grow in size. We won’t ever hit the golden ratio _exactly_, since it’s an irrational number; but the larger our Fibonacci number, the closer we’ll get to it as we compare one ratio to&nbsp;another.

The Fibonacci sequence and the Golden Spiral [exist all around us](http://jwilson.coe.uga.edu/emat6680/parveen/fib_nature.htm)â€Š–â€Šin the arms of a starfish, the patterns of a seashell, the branching of a treeâ€Š–â€Šand even _within_ usâ€Š–â€Šinside the human ear, within the proportions of our fingers, and even the ratio of the human arm! My personal favorite example of this sequence in nature comes from my favorite flower: the sunflower.

![](https://cdn-images-1.medium.com/max/1024/1*gcz8UYcLb6aNm4OLHS0dbw.jpeg)<figcaption>Photo by <a href="https://unsplash.com/photos/vYg2mWKqQcU?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Marjorie Bertrand</a> onÂ <a href="https://unsplash.com/?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption>

According to [research from](http://www.sciencemag.org/news/2016/05/sunflowers-show-complex-fibonacci-sequences) _The_ _American Association for the Advancement of&nbsp;Science,_

> The telltale sign is the number of different seed spirals on the sunflower’s face. Count the clockwise and counterclockwise spirals that reach the outer edge, and you’ll usually find a pair of numbers from the sequence: 34 and 55, or 55 and 89, orâ€Š–â€Šwith very large sunflowersâ€Š–â€Š89 and 144. Although the math may be beautiful, plant biologists have not worked out a mechanistic model that fully explains how the sunflower seed patterns&nbsp;arise.

And guess what? There’s yet _another_ way that this pattern is connected to AVL trees, which is perhaps what makes them so damn&nbsp;golden.

Time to find&nbsp;out!

### The golden (tree height)&nbsp;ratio

What is the final petal in this metaphorical flower of Fibonacci?

In order to bring it all home, we’re going to need to go back to where we started: determining the relationship between the minimum number of nodes and the height of an AVL tree. We’ve looked at two different formulas: first, we figured out how we could determine the height based on the minimum number of nodes we needed; then, we determined at the number of nodes we’d need based on the height that knew a tree&nbsp;had.

![](https://cdn-images-1.medium.com/max/1024/1*GzVH6CTNESDu4_JQ1xBICg.jpeg)<figcaption>Log base Ï† has a unique relationship to the height ofÂ nodes</figcaption>

Well, it turns out that the Fibonacci sequence and the golden ratio were under the surface of both of these formulas the entire&nbsp;time!

When we used the minimum number of nodes in a tree in order to determine its height, what we were _really_ doing was taking the log, with a base of the golden ratio, of the minimum number of nodes, which gave us an approximation of the height of the tree. In fact, this is exactly where the [logarithmic complexity](https://dev.to/vaidehijoshi/looking-for-the-logic-behind-logarithms) of an AVL tree comes from! We just generally don’t refer to the base, so most of the time it’s never explicitly stated that we’re taking _log_ _base&nbsp;1.618._

For example, when we determined that a tree with a minimum number of 54 nodes would give us a height of 8, what we were _really_ doing was taking the _log base 1.618 of 54_, which _approximately_ yields us 8.29, which rounds to an integer value of&nbsp;8.

If we were to graph the relationship between the number of nodes and the height of the tree, we would effectively be [graphing](http://www.wolframalpha.com/input/?i=graph+log+base+golden+ratio+of+x) _log base golden ratio of n_, where _n_ is the number of nodes in a&nbsp;tree.

![](https://cdn-images-1.medium.com/max/1024/1*dn_YP2516xfWXmRHpLI-vA.jpeg)<figcaption>As the number of nodes in an AVL tree grows linearly, the height grows logarithmically.</figcaption>

Another way of thinking about this is that the relationship between the number of nodes and the height of a tree is **_logarithmic_**.

> As the minimum number of nodes in an AVL tree grows linearly, the height of the tree grows logarithmically.

If you remember [learning about logarithms](https://dev.to/vaidehijoshi/looking-for-the-logic-behind-logarithms) earlier in this series, then you might recall that a logarithmic function is the inverse of an exponential function. So, what about the second formula we looked at, where we determined the minimum number of nodes based on the height of the&nbsp;tree?

The relationship is going to be the inverse of a logarithmic relationship: it’s going to be _exponential_. We can see this play out in the illustration below.

![](https://cdn-images-1.medium.com/max/1024/1*OpXbFgjwmEiesFw_pwhqZQ.jpeg)<figcaption>As the height of an AVL tree grows linearly, the number of nodes it needs grows exponentially.</figcaption>

As the height of an AVL tree grows linearly, the minimum number of nodes it has will grow _exponentially_ (approximately, of&nbsp;course).

We can see that each time that we took the height of a tree as the input and used it to derive the minimum number of nodes for an AVL tree of our inputted height, we were effectively raising the golden ratio to the power of our height,&nbsp;_h_.

For example, when we wanted to calculate the minimum number of nodes for an AVL tree with a height of 8, we raised Ï† to the power of 8, which gave us _approximately_ 46.98. Remember, since we’re dealing with a rounded version of an otherwise irrational number, as our numbers get larger, our approximations have a much higher margin of error. This explains why our calculation for a tree with a height of 2, 3, 4, or 5 are much more accurate than our calculation for a tree with a height of 8. If we were to graph these results, we would [actually be graphing](http://www.wolframalpha.com/input/?i=graph+golden+ratio%5Ex) _the golden ratio raised to the power of h_, the height of our&nbsp;tree.

If you’re feeling amazed, in awe, and completely in wonder of what you just learned, don’t worryâ€Š–â€ŠI felt the exact same way, too. I don’t think I’ll ever think of a sunflower or an AVL tree in the same way, ever&nbsp;again.

(And, if I’ve done my job well, neither will&nbsp;you.)

### Resources

I had trouble containing all my excitement about Fibonacci, golden ratios, and AVL trees, and did a whole lot of research on all three of these topics. If you’re as fascinated and amazed by them as I am, you’ll enjoy the links&nbsp;below.

1. [Data Abstractions: AVL Trees](https://courses.cs.washington.edu/courses/cse332/11wi/lectures/cse332-11wi-lec07-AVL.pdf), Professor Ruth&nbsp;Anderson
2. [Fibonacci Sequence](https://www.mathsisfun.com/numbers/fibonacci-sequence.html), Math Is&nbsp;Fun
3. [Maximum Height of an AVL Tree](http://lcm.csa.iisc.ernet.in/dsa/node112.html), CSA Department, IISc, Bangalore
4. [15 Uncanny Examples of the Golden Ratio in Nature](http://io9.gizmodo.com/5985588/15-uncanny-examples-of-the-golden-ratio-in-nature), George&nbsp;Dvorsky
5. [Fibonacci Number,](http://mathworld.wolfram.com/FibonacciNumber.html) Wolfram&nbsp;Research
6. [AVL Trees](http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html), Professor Eric Alexander

* * *


_This post was originally published on [medium.com](https://medium.com/basecs/finding-fibonacci-in-golden-trees-1c8967b1f47a)_