Before we can get into how trees can be utilized in real world programs it is helpful to take a step back and walk through the basic operations for the tree data structure.
When it comes to coding interviews, being able to properly answer questions related to trees can be the difference between getting the job and being passed over. So with that in mind it’s critical to have a strong knowledge of how to work with this data structure.
Operations for the Tree Data Structure
There are six fundamental tools that are utilized when working with trees. These operations are what allow trees to be the powerful computer science mechanism that they are.
The six operations for the tree data structure are:
A few of these, such as adding and deleting are self explanatory. However concepts such as
grafting may take a little more study.
We’ll cover each of these operations in detail while studying trees. For right now let’s take a high level view at the behavior of each operation.
While working with the tree data structure, one of the most common tasks is enumerating through the tree. Essentially this means that your algorithm can traverse through the tree.
Enumerating can take a few forms.
A straightforward example would be to find the path from a root node in a binary tree to another node (this also falls into the realm of searching, but this still requires enumerating through the tree).
However a more practical example would be if we were creating a mapping application. If we had a set of cities, represented as nodes, and needed to generate a route that took the shortest path… this is also enumeration.
In this example our algorithm will have to navigate our tree of geographical nodes in order to find the most efficient route. This is the type of algorithm that the creators of applications such as Google Maps work on daily.
Next on the list of operations for the tree data structure is searching. Searching within trees, especially binary search trees, is one of the tools that makes working with this data structure so powerful.
Trees specialize in organizing data in an efficient manner. Imagine that you are in charge of doing laundry in your home. Will you be able to find a matching pair of socks faster if you first have all of the socks in their own pile? Or would it be more efficient to simply look at every…. single… piece of clothing? Of course it would be faster if your socks are all in the same pile.
Searching within trees works the same way as our laundry example. A tree allows you to efficiently organize your data in a way that searching can be exponentially more efficient compared with other data structures.
When it comes to adding to a tree, the concept is straightforward. You simply add a new node to the structure. The key is that the element has to follow the rules of the tree.
For example, if you were to add a new city to the routing application, it would have to be added in a manner that did not cause a nasty detour. For example, if you wanted to add a visit to San Francisco, you wouldn’t want to add the new location while in the middle of the trip since this would dramatically decrease the efficiency of the route (and you’d have some annoyed drivers).
Instead you would need to ensure that when you add new nodes they follow the rules your routing algorithm has already set in place.
In deleting nodes from a tree, the process of removing the nodes typically requires you to implement a set of processes for ensuring that the tree remains stable. This can be a complex process, such as ensuring that a binary search tree remains balanced after removing a node (we’ll discuss this in detail later on). Or it can be as straightforward and updating a reference on a single node.
For example, going back to our mapping tree, let’s imagine that we removed our stop in Dallas. All we would have to do is:
- Delete the
- Update the reference so that the
Scottsdalenode points to the
Many new students eyes glaze over when they hear the term
pruning in relation to data structures. However don’t tune our now, pruning is actually a relatively straightforward process when you think about it practically.
Pruning is the process of removing an entire section of a tree. So for our mapping application, let’s imagine that we had a tour of the Northwest US included in our route.
In order to
prune the tree we simply removing a section from the tree. In this case we’d remove the nodes associated with the Northwest portion of the trip.
If the concept of
pruning makes sense, then you will pick up on
grafting quite easily. The concept of
grafting is adding an entire section to a tree.
In this example we’re adding a new section of the tree that includes taking a tour of New England. So
grafting is simply adding new sub sections to a tree. As with adding a single element, the key to grafting is ensuring that the new section follows the rules of the rest of the tree.