Trees are naturally recursive data structures, and because of this, we cannot access their elements like we might access the elements of a vector or array. Instead, we need to use more interesting methods to work through each element. This is often called Tree Traversal, and there are many different ways to do this. For now, we will restrict the discussion to two common and related methods of tree traversal: Depth-First and Breadth-First Search. Note that trees vary greatly in shape and size depending on how they are used; however, they are composed primarily of nodes that house other, children nodes, like so:
{% method %}
{% sample lang="jl" %}
import:3-7, lang:"julia"
{% sample lang="cpp" %}
import:12-15, lang:"cpp"
{% sample lang="cs" %}
import:6-10, lang:"csharp"
{% sample lang="c" %}
import:7-11, lang:"c"
{% sample lang="java" %}
import:112-128, lang:"java"
{% sample lang="js" %}
import:1-10, lang:"javascript"
As a note, a node struct is not necessary in javascript, so this is an example of how a tree might be constructed.
{% sample lang="py" %}
import:1-4, lang:"python"
{% sample lang="scratch" %}
Because of this, the most straightforward way to traverse the tree might be recursive. This naturally leads us to the Depth-First Search (DFS) method:
{% method %} {% sample lang="jl" %} import:9-16, lang:"julia" {% sample lang="cpp" %} import:17-24, lang:"cpp" {% sample lang="cs" %} import:33-44, lang:"csharp" {% sample lang="c" %} import:37-45, lang:"c" {% sample lang="java" %} import:20-26, lang:"java" {% sample lang="js" %} import:12-19, lang:"javascript" {% sample lang="py" %} import:17-22, lang:"python" {% sample lang="scratch" %}
At least to me, this makes a lot of sense. We fight recursion with recursion! First, we first output the node we are on and then we call DFS_recursive(...) on each of its children nodes. This method of tree traversal does what its name implies: it goes to the depths of the tree first before going through the rest of the branches. In this case, the ordering looks like:
Note that the in the code above, we are missing a crucial step: checking to see if the node we are using actually exists! Because we are using a vector to store all the nodes, we will be careful not to run into a case where we call DFS_recursive(...) on a node that has yet to be initialized; however, depending on the language we are using, we might need to be careful of this to avoid recursion errors!
Now, in this case the first element searched through is still the root of the tree. This type of tree traversal is known as pre-order DFS. We perform an action (output the ID) before searching through the children. If we shift the function around and place the data output at the end of the function, we can modify the order in which we search through the tree to be post-order and look something like this:
{% method %} {% sample lang="jl" %} import:18-26, lang:"julia" {% sample lang="cpp" %} import:26-31, lang:"cpp" {% sample lang="cs" %} import:46-57, lang:"csharp" {% sample lang="c" %} import:47-53, lang:"c" {% sample lang="java" %} import:33-40, lang:"java" {% sample lang="js" %} import:21-28, lang:"javascript" {% sample lang="py" %} import:25-30, lang:"python" {% sample lang="scratch" %}
In this case, the first node visited is at the bottom of the tree and moves up the tree branch by branch. In addition to these two types, binary trees have an in-order traversal scheme that looks something like this:
{% method %} {% sample lang="jl" %} import:28-43, lang:"julia" {% sample lang="cpp" %} import:34-52 lang:"cpp" {% sample lang="cs" %} import:59-83, lang:"csharp" {% sample lang="c" %} import:55-73, lang:"c" {% sample lang="java" %} import:47-64, lang:"java" {% sample lang="js" %} import:30-51, lang:"javascript" {% sample lang="py" %} import:34-45, lang:"python" {% sample lang="scratch" %}
The order here seems to be some mix of the other 2 methods and works through the binary tree from left to right.
Now, at this point, it might seem that the only way to search through a recursive data structure is with recursion, but this is not necessarily the case! Rather surprisingly, we can perform a DFS non-recursively by using a stack, which are data structures that hold multiple elements, but only allow you to interact with the very last element you put in. The idea here is simple:
- Put the root node in the stack
- Take it out and put in its children
- Pop the top of the stack and put its children in
- Repeat 3 until the stack is empty
In code, it looks like this:
{% method %} {% sample lang="jl" %} import:45-56, lang:"julia" {% sample lang="cpp" %} import:55-70, lang:"cpp" {% sample lang="cs" %} import:85-98, lang:"csharp" {% sample lang="c" %} import:75-93, lang:"c" {% sample lang="java" %} import:67-81, lang:"java" {% sample lang="js" %} import:53-60, lang:"javascript" {% sample lang="py" %} import:48-53, lang:"python" {% sample lang="scratch" %}
All this said, there are a few details about DFS that might not be ideal, depending on the situation. For example, if we use DFS on an incredibly long tree, we will spend a lot of time going further and further down a single branch without searching the rest of the data structure. In addition, it is not the natural way humans would order a tree if asked to number all the nodes from top to bottom. I would argue a more natural traversal order would look something like this:
And this is exactly what Breadth-First Search (BFS) does! On top of that, it can be implemented in the same way as the DFS_stack(...) function above, simply by swapping the stack for a queue, which is similar to a stack, except that it only allows you to interact with the very first element instead of the last. In code, this looks something like:
{% method %} {% sample lang="jl" %} import:58-69, lang:"julia" {% sample lang="cpp" %} import:73-86, lang:"cpp" {% sample lang="cs" %} import:100-113, lang:"csharp" {% sample lang="c" %} import:95-113, lang:"c" {% sample lang="java" %} import:83-97, lang:"java" {% sample lang="js" %} import:62-69, lang:"javascript" {% sample lang="py" %} import:55-60, lang:"python" {% sample lang="scratch" %}
Here is a video describing tree traversal:
{% method %} {% sample lang="jl" %} import, lang:"julia" {% sample lang="cpp" %} import, lang:"cpp" {% sample lang="cs" %}
import, lang:"csharp" {% sample lang="c" %}
import, lang:"c" {% sample lang="java" %}
import, lang:"java" {% sample lang="js" %} import, lang:"javascript" {% sample lang="py" %} import, lang:"python" {% sample lang="scratch" %}
The code snippets were taken from this Scratch project
The code examples are licensed under the MIT license (found in LICENSE.md).
The text of this chapter was written by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
- The image "DFSpreorder" was created by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
- The image "DFSpostorder" was created by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
- The image "DFSinorder" was created by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
- The image "BFSsimple" was created by James Schloss and is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.
After initial licensing (#560), the following pull requests have modified the text or graphics of this chapter:
- none