Data Structures Pt.5: “Trees”
If you are in the process of your job search and job interviews, I am sure you’ve come across the word Data Structures. What are they and how can we use them in our daily programming. I’ve started a blog series on Data Structures, touching on a different type each week. We will be using Javascript as the programming language as we dive into Data Structures. Last time we discussed Linked List this time we will talk about Trees. I would like to add is while data structures are common in a tech interview, we find ours mostly working with arrays and objects, but they are important for us to understand on an algorithm level. So let’s get started.
What is a Tree?: A tree in programming has a strong representation of a tree in real life. Fact, a tree data structure looks like a tree turned upside down. These particularly become relevant when moving on to full-stack development. There are several different types of trees out there, but that mostly depends on how the trees are balanced with their node structure.
The parts of a Tree: Here in this diagram we see a data structure of a Tree. Firstly every box that we see can be referred to as a Node. Every Node holds some sort of data and a reference to its Children. The data belonging to the Node, strictly depends on your use of the tree, in your scenario, via strings, arrays, objects, etc. A child is any Node that is directly beneath any Node. Likewise, any Node on top is referred to as the Parent Node. Thus we get a parent-child relationship, in which the Tree is designed. While this is the case, we tend to refer to our starting Node as the Head Parent node, which resides at the top of every Tree. For the case of Children, if the Children belong to a particular parent they are referred to as Siblings. In this particular case, Children containing the data 1,7,2 are Siblings. While they are on the same level as the Children containing data of 44 and 11 (who are their Siblings), are not Siblings of Children 1,7,2.
Creating a Tree:
Node Class: To create a Tree, we first need to create a Node Class, because after all a Tree is made of Nodes. So as usual we have our Node Class, with its constructor function, that takes in the argument of data. We will set data to itself and include a children’s property that is equal to an empty array. Our two methods for the Node Class will be, add and remove, refer to my code, to get a better understanding. Take note we will keep our add and remove methods, defined in the Node Class, that way we can specify which Node we want to add or remove elements from.
Tree Class: On to our Tree Class, we will primarily be using our Node Class to implement our methods, such as add, remove, and peek. In easy terms, we are creating a new node and adding it to the tree. Even as in nature, every tree begins with a seed of course, which is a casing for the root gene. We start our Tree Class by constructing root to null, which we will manually assign to our node we have created (see code). Please take note that the Tree class strictly maintains the traverse methods.
Tree Traversal: When presented with a Tree, your main objective is to traverse the Nodes of a Tree, to obtain their data, similar to our linked list situation. Now when we speak of Tree traversal, there are two distinct ways of carrying this process out.
Breadth-First Traversal: Type one would be Breath-First Traversal. With Breath-First Traversal, we iterate at each level of the Tree from left to right. Starting with Head Parent Node, we move down one level at a time, still left to right. Although if the Siblings on that level to not have a relationship with the Siblings next to then we stick to our order of left to right. Note Breath-First Traversal function, takes in a function.
Depth-First Traversal: Now this is a lot harder to explain, so stick with me please, and I’ll do the best I can. With Depth-First Traversal, we start again with our Head Parent Node. Next, we move down the Nodes one parent at a time, starting with the left side. Here we refer to their Children, before moving on to the next parent, and so on. My diagram does a bit better job of explaining things. Note Depth-First Traversal function, takes in a function.
Wrapping Up: I’d like to take note of how useful the ES6 spread operator is, and how it saves us multiples lines of code. Now depending on your situation, you may need Breath-First or Depth-First Traversal, or both, but always one or the other. Next, we will look at examples of when to use Breath-First and or Depth-First. I hope you enjoyed the read. I know it’s long, but I try my best to make this easy to understand. So props to you for sticking through, see you soon.
