Why Fibonacci is the perfect starting point to figure out Data structure (Part 1)
To speak on my own, when I first came across the famous Fibonacci numbers sequence algorithm I Immediately considered It a useless kind of algorithm, which unique purpose was to understand the recursion pattern better.
By the way, just some years later I realised It’s the perfect entry point not just to unroll the recursion, which is dramatically helpful when it comes to specific Data structures flowing, but also to start engaging with algorithms complexity through Binary Tree.
Let’s try to delve into this unusual topic.
A short preview
Whether you’re a freshman in the computer science industry or an experienced Senior, you must own a great knowledge and understanding of both Data Structure and Algorithms, which are some of the main pillars of the overall Software Development craftmanship.
The combination of these tools is enough to figure out If you’re just a good coder or a proficient one. Needless to say, the target is always to create software that works, but It’s equally important to create a piece of code that’s efficient, both when it comes to time and space complexity.
That being said, Let’s give a nuance at the Fibonacci algorithm, a little closer.
How is the Fibonacci numbers algorithm designed?
If you’ve just a basic knowledge of coding, you perfectly know that the Fibonacci Algorithm is in this way defined:
The above code snippet showcases the Fibonacci computation in its simplest form, with just one base case along with its inductive case. Furthermore, the overall complexity of this algorithm implementation can be described as T(n) = 2 + T(n — 1) + T(n-2), where 2 is given by the complexity of the base case, composed of just 2 and 1, whereas the second half of the complexity is output by the complexity of the induction case application.
Whether you start drawing a visual way to concept this algorithm, you’re going also to compound a precise Data structure: Binary Tree, a cornerstone of not just algorithm but also the base of how copious software and social networks are made, like Facebook and Google Maps.
What is a Binary tree?
Generally speaking, a Tree is basically a Data structure which stores at least a node, which, in turn, can point to other nodes or no one at all.
In this specific case, you have to grapple with a node that stores two pointers, then you’re going to build a Binary Tree.
A Binary tree basic implementation is the following:
The minimum information a node store are the following:
- Information: The Information the node carries
- Left-node pointer: Pointer to the left child.
- Right-node pointer: Pointer to the right child.
In its basic form, a node contains some Information, but its two internal pointers can point to NULL. In this case, the binary tree is going to be made of just a node, which it’s at the same time both the parent and the leaf of it.
Thank you very much for reading so far.
Want to Connect?If you want to reach me to discuss a project or simply chat, here’s my GitHub link.
