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.

Tree Data Structure Operations

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:

• Enumerating
• Searching
• Adding
• Deleting
• Pruning
• Grafting

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 and graphs. For right now let’s take a high level view at the behavior of each operation.

devCamp Note: For the real world examples I'm going to switch between the Tree and Graph data structures. The reason for this is because a Tree is actually a type of Graph. Typically graphs are utilized more often in real world development compared with trees. And since this course focuses on bridging the gap between software development and the study of algorithms, I chose to combine the examples. However it is important to understand that a tree is a special type of a graph. If you are into fancy words, a tree is an acyclic graph, which means that it doesn't have any cycles. The key to remember is that a tree is a minimally connected graph because there is only one path between each child and parent node (hence the inability for cyclic behavior).

Enumerating

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.

Searching

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.

Adding

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.

Deleting

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 Dallas node.
• Update the reference so that the Scottsdale node points to the Houston node.

Pruning

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.

Grafting

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.

Summary

You should now have a good understanding for the operations that are performed with the tree data structure, including: enumerating, searching, adding, deleting, pruning, and grafting.

What's Next?

In the next guide we're going to start examining the various types of trees that can be implemented in real world programs.