Traversals
With the linear data structures we've seen previously, we've seen that it's possible to traverse them, which is to say that we visit each data element and do something with it. For example, a linked list traversal is an algorithm in which we visit every element stored in the linked list exactly once. The word "visit" may seem a little bit strange here, but that's because it's abstract: What we do to each element in a traversal depends on why we're doing the traversal in the first place. We might be traversing the elements because we want to store them in a file, or because we want to send them across a network, or because we want to search to see whether one of them has some characteristic we're interested in. Regardless, though, the underlying idea is the same: Use an algorithm that can get you to every element in the list exactly once, and tailor your idea of "visiting" to your specific needs.
In C++ terms, traversing a linked list might look something like this:
Node* current = head;
while (current != nullptr)
{
visit(current->data);
current = current->next;
}
Once you're comfortable with the idea of using pointers in this way, the approach is a straightforward one; at any given time, we keep a pointer to the node we're currently looking at, then move it gradually forward throughout the list, one step at a time. Note, too, that we're visiting the data in each node, not the node itself; the node is just an implementation detail, while the data is what's actually important.
When you consider how you might traverse a tree, though, the idea isn't quite so simple. At every step in the process of traversing a linked list, there's no question about where you should go, since every node has only one node that directly follows it. In a tree, however, the problem is more complex. Nodes have multiple children. Some nodes have no children. How do you know which way to go? What do you do when you hit a dead end? How do you ensure you never visit the same node twice?
Tree traversals
A tree traversal is an algorithm that visits the data element in every node in a tree exactly once. Again, the notion of "visiting" is an abstract one; what you do when you visit a data element can be anything you need done, but it doesn't change the core algorithm used to find every node and ensure that its data element is only visited once. So we should concentrate on that algorithm, because once we understand that, we can use it for any purpose we'd like.
The first question we need to consider is the order in which we'd like to find the nodes. In some cases, we don't care; any order will do. In others, the data is structured in a particular way — the parent/child relationship has a particular meaning — and we want to visit it in an order reflected by that structure. So, generally, we should consider the available options, understand the tradeoffs inherent in each, and then we'll be able to make a practical choice given a real problem we need solved.
While there are lots of ways to traverse a tree, they fall broadly into two categories: breadth-first and depth-first. The distinction, stated simply, is between the idea of working our way across before working our way downward (that's "breadth-first") and the idea of working our way downward as far as that takes us before working our way across (that's "depth-first").
As we proceed with our discussion, we'll use the same tree we saw in the previous Notes and Examples page, duplicated below.
Breadth-first tree traversals
A breadth-first tree traversal reaches nodes in the order of their depth in the tree — the root first, then all nodes that are children of the root (i.e., at depth 1), then all nodes that are children of those nodes (i.e., at depth 2), and so on. Many trees have no explicit notion of ordering of the children of each node, in which case it's not important what order these children are reached, but, to keep things simple for the sake of this conversation, we'll work left-to-right in the diagram whenever given a choice. With that clarification in place, we would say that the data elements would be visited in the following order:
X Q F D C N R S M H L
Conceptually, that's all there is to it. However, there's a more interesting question we should consider: How do you implement something like this? And, once we understand that, how much time and memory does it require to do it?
Central to the implementation of a breadth-first tree traversal is a queue of the nodes that, at any given time, are the ones that we've not yet considered, but should consider before any others. We'll dequeue nodes from that queue, visit their data, then enqueue additional nodes afterward, using the following algorithm.
let Q be an empty queue
if the tree is not empty:
enqueue the root of the tree into Q
while Q is not empty:
dequeue a node n from Q
visit n's data
enqueue n's children into Q
Before you proceed, work through this algorithm on paper and convince yourself that it indeed visits every node's data element exactly once. Pay attention to its behavior as you go; for example, note that the nodes on each level aren't enqueued until after the nodes on the previous level have all been enqueued already. It's the use of a queue that gives this algorithm its breadth-first characteristic.
Asymptotic analysis
A key property of this algorithm is that no node on level i is enqueued until its parent is dequeued. In fact, we can observe that no node on level i is enqueued until after all nodes on the level i − 1 are enqueued already. Further, we can observe that no node on level i is enqueued until after all nodes on the level i − 2 have been dequeued (because only then will all nodes on level i − 1 have been enqueued).
From these facts, there are two things we know for sure:
- The nodes will be dequeued in level order, making this a valid breadth-first traversal.
- When we've finished with one level of the tree, all of the nodes on the level below it will be in the queue and no others.
Now come the two key questions: How much time is required, and how much memory is required? Let's take each of these in turn.
Measuring the amount of time required isn't quite as straightforward as some of the algorithms we've seen previously. If you consider that it's centered around a loop, you might first imagine that you would need to count how many loop iterations there will be. However, it's not that simple, because some loop iterations will take longer than others; some nodes have more children than others, while others have none. But if we consider, in total, everything the algorithm does, a few facts emerge:
- The total number of nodes that are dequeued across all loop iterations is n, the number of nodes in the tree. Dequeuing each takes Θ(1) time, if we assume a good queue implementation, so this takes a total of Θ(n) time.
- The total number of nodes enqueued across all loop iterations is also n. So, again, this is a total of Θ(n) time.
- The data in all n nodes is visited, as well. We'll say that each visit step takes Θ(1) time — or, at the very least, that the amount of time it takes to visit one data element is not a function of any aspect of the tree (i.e., how many nodes it has, what its height is, etc.). So, again, a total of Θ(n) time is spent.
So, in total, it will take Θ(n) time to run the complete traversal, regardless of the tree's shape.
Measuring how much memory we need — above and beyond the tree, which is something that already exists and isn't part of the algorithm itself — is mainly a question of how large the queue can get. One thing we could say is that it will take O(n) memory, because if the tree was flat (i.e., one root node with every other node a child of the root), essentially every node would end up in the queue. But this, while true, is somewhat misleading; we could do better if we described the tree in terms of something other than how many nodes it contains.
We'll say that the tree has n nodes, a height of h, and a width of w, where the width is defined as the maximum number of nodes on any level. Given these variables, we can say something more powerful. Each time we finish with one level of the tree, the next entire level will be in the queue. So, the maximum amount of memory we'd use is proportional to the tree's width, or Θ(w). (You could also reasonably say O(w), in the sense that you won't be using the memory the entire time the algorithm runs. It depends on whether you're talking about "How much memory would need to be available so that I wouldn't run out?" or "How much memory would I be using at any given time while the algorithm runs?")
Depth-first tree traversals
A depth-first tree traversal performs a traversal of each entire subtree before traversing the others. Thought differently, it follows one path until it reaches a leaf, then backtracks and tries another path, and so on. As with breadth-first tree traversals, in trees that have no explicit ordering of the children of each node, it's not important what order the subtrees are traversed, but we'll assume that we traverse them in left-to-right order when not specified.
One important question in a depth-first tree traversal is when we do the visiting while we traverse. Broadly speaking, there are two choices:
- Visit the data in a node first, then traverse its subtrees. We call this a preorder traversal, because the visit step happens before (i.e., pre) the subtrees.
- Traverse a node's subtrees first, then visit its data. We call this a postorder traversal, because the visit step happens after (i.e., post) the subtrees.
Neither of these is right or wrong; each is a choice you might reasonably make, depending on the reason why you're traversing the tree. If the distinction doesn't matter, you can choose either; if, on the other had, it matters (and we'll see examples later this quarter), you'd want to make the appropriate choice.
The algorithms are most easily written recursively, with recursive calls made as you work your way down the tree, and returning from the recursive calls causing backtracking. You could also write these iteratively, but you'd then need to maintain your own stack — the same stack that is provided implicitly by the run-time stack in a recursive function.
preorder(Tree t):
visit(data in root of t)
for each subtree s of t:
preorder(s)
postorder(Tree t):
for each subtree s of t:
postorder(s)
visit(data in root of t)
Before you proceed, work through these two algorithms on paper and convince yourself that they indeed visit every node's data element exactly once. Pay attention to their behavior as you go, noting how the use of recursion gives this algorithm its depth-first characteristic.
Asymptotic analysis
The first step in analyzing these algorithms is realizing that they both perform exactly the same operations, albeit in a different sequence. The same recursive calls will be made, the same visits will be done; the only difference is when. For this reason, the analysis of one is essentially the same as the analysis of the other, so we'll just consider preorder, and see if we can determine how much time and memory would be required by it.
Since the preorder algorithm is recursive, we could try to write a recurrence that describes how much time it spends, then solve that recurrence. However, this turns out to be a problematic approach, because the recurrence we might write would be highly dependent on the shape of the tree. So, instead, let's consider the overall behavior of the algorithm at once. As we saw when we analyzed breadth-first traversals, a few key facts emerge:
- There will be exactly one call to preorder for every node in the tree. The first of these is the one that started the process; the rest are recursive calls that are made throughout.
- The total number of iterations across all of the for each loops is n − 1, since there are n − 1 nodes in the tree other than the root.
- Every node's data is visited exactly once, so there is a total of n visit steps being done.
From these facts, we can see that, in a tree of n nodes, Θ(n) time will be spent in a preorder traversal of that tree — a linear amount of time to perform the visit steps, a linear amount to perform all of the recursive calls, and a linear amount to iterate through all of the loops.
Considering memory usage, the main factor is the depth of the recursion. While each call to preorder uses a constant amount of memory — say, a pointer to some node and another pointer or index that iterates through the subtrees — there will be potentially many calls to preorder active at any given time. Again, let's assume the tree has n nodes, a height of h, and a width of w. In this case, the height of the tree is the important thing; that determines how deep the recursion can go, since, at worst, you'll have one recursive call active for every node in some path in the tree — and the height of the tree is the length of its longest path. So, in total, we'd say that we need a maximum of Θ(h) memory — or, thought differently, O(h) memory at any given time, since we won't always need all of it. (It's important to remember that the run-time stack is still memory, so the fact that recursion might need to go h levels deep implies that we'll need h stack frames on the run-time stack. That's the cost we're measuring in this case.)