5
$\begingroup$

Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?

$\endgroup$
  • 3
    $\begingroup$ pre-,in-, and post-order are kind of DFS and see the applications $\endgroup$ – kelalaka Dec 17 '18 at 19:39
  • 1
    $\begingroup$ You can use breadth-first if you like which is sometimes called "level-order" in a tree context. You can traverse graphs in orders other than breadth-first as well. What ordering you used depends on your goals. It is far from the case that one ordering (in trees or graphs) suffices for all purposes. $\endgroup$ – Derek Elkins Dec 17 '18 at 23:48
7
$\begingroup$

Different traversals of a binary tree exist to suffice different data dependencies between the nodes.

Let's have a comparison between different traversals of a tree. Note that aside from in-fix traversal, the tree doesn't have to be binary.

In case of Postorder, we process the descendants of a node before the node itself, meaning that we want to send some data from the descendants to the ancestors to be able to process the ancestors. For example if you want efficiently to calculate for each node $n_i$ the weight of the subtree rooted at $n_i$, which is the sum of the weights of all descendants of $n_i$ including $n_i$.

In case of Preorder, you process the predecessors before the descendants. One use case is broadcasting data to all descendants of each node in the tree. For example, if you want count the number of predecessors of each node with some characteristic, you propagate the counter of each node to its children and each child add one if it has the characteristic itself.

In case of Inorder you might have a left-right order between the nodes of the tree (Example: binary search tree), and might be interested in visiting the elements according to this order (Printing the keys of a binary search tee in ascending order).

Finally, in case of BFS, we consider the tree as levels, level $l_i$ has all vertices with depth $i-1$, which is at distance $i-1$ from the root of an unweighted tree. BFS has a lot of use-cases. Here we are interested in processing all nodes of each level consequently (starting from the smallest level). Most common use cases are the ones where we want to process the closer vertices to the root before the farther ones for example if we want to assign ids to the vertices so that for two vertices $n_i, n_j$ if $i < j$, $n_j$ is not closer to the root than $n_i$.

Note that in some cases you might be interested in two consequent traversals for example a post-order to gather data from the whole tree in the root and a following pre-order to broadcast the data to each node in the tree in total linear time in the size of the tree.

Note In some cases any of the traversals suffices, if all nodes are independent of each other and you are only interested in visiting all nodes of the tree(For example, to calculate the depth of each node you can use BFS or Preorder with no remarkable differences). However, some times you might still be interested in the order you are visiting the nodes even if there is no data-dependencies between the nodes (For example printing mathematical expression in polish notation vs. infix notation. see link).

Note One interesting application is Euler tour technique in parallel computing. By setting the right weights on the right edges you get pre-order, post-order and the depth of the nodes of a tree. see link.

$\endgroup$
  • $\begingroup$ On the penultimate note, preorder has the advantage over BFS of requiring O(1) extra memory vs O(n). $\endgroup$ – Peter Taylor Jan 24 at 14:16
2
$\begingroup$

As Narek Bojikian explains, it depends on the use case: often, any traversal order will do, but sometimes, it makes a big difference. He doesn't provide concrete examples, so I will provide one, using the Unix find command.

The Unix find command lets you traverse a directory tree and execute arbitrary commands for each file it encounters.

Let's create a directory:

$ mkdir d

Now let's traverse that directory tree (it's empty), no deeper than depth 2, and for each file we encounter, execute mkdir to create the subdirectories a and b:

$ find d -maxdepth 2 -exec mkdir \{}/a \{}/b \;

This should just create the directories d/a and d/b, right?

Let's see. Without arguments, find just prints the names of the files it encounters:

$ find d
d
d/a
d/a/a
d/a/a/a
d/a/a/b
d/a/b
d/a/b/a
d/a/b/b
d/b
d/b/a
d/b/a/a
d/b/a/b
d/b/b
d/b/b/a
d/b/b/b

We got a lot more than just d/a and d/b. Why?

As you can see from this listing, find traverses the directory tree using depth-first search: it prints d/a/a before d/b.

More specifically, it uses preorder traversal: it prints d before d/a.

It turns out that in cases where we care about the order of processing, this is the most commonly wanted order. For instance, if we just want a listing of filenames, this produces them in lexicographical order, which is usually what we want.

The preorder traversal explains why the first find command created so many directories: it executes the mkdir command for a directory before traversing its contents, which by then include the newly created subdirectories a and b.

So this is a nice way to create a directory of arbitrary depth (specified by the -maxdepth argument).

What if we want to traverse a directory tree and only create a and b subdirectories in each pre-existing directory?

The answer: that's exactly what postorder traversal will produce:

find d -depth -exec mkdir \{}/a \{}/b \;

The -depth option means: use postorder traversal instead of the default preorder traversal. (It should have been called -postorder.) This command would have created just d/a and d/b.

But OK, we've created this whole directory tree. Let's remove it. We can do this easily, by calling rmdir on each directory in it.

First try:

$ find d -exec rmdir \{} \;
rmdir: failed to remove 'd': Directory not empty
rmdir: failed to remove 'd/a': Directory not empty
rmdir: failed to remove 'd/a/a': Directory not empty
find: ‘d/a/a/a’: No such file or directory
find: ‘d/a/a/b’: No such file or directory
rmdir: failed to remove 'd/a/b': Directory not empty
find: ‘d/a/b/a’: No such file or directory
find: ‘d/a/b/b’: No such file or directory
rmdir: failed to remove 'd/b': Directory not empty
rmdir: failed to remove 'd/b/a': Directory not empty
find: ‘d/b/a/a’: No such file or directory
find: ‘d/b/a/b’: No such file or directory
rmdir: failed to remove 'd/b/b': Directory not empty
find: ‘d/b/b/a’: No such file or directory
find: ‘d/b/b/b’: No such file or directory

Clearly, that doesn't work: we're traversing in preorder again, so we're calling rmdir on a directory before trying to visit its subdirectories. Once again, the resolution is to visit in postorder instead:

$ find d -depth -exec rmdir \{} \;
$ find d
find: ‘d’: No such file or directory

That's better. The whole tree has been removed.

So having the choice between preorder and postorder directory tree traversal is clearly useful. That's why find gives us both.

What if we want to use breadth-first traversal instead? Too bad, find doesn't have an option for that. Why not?

One reason: I've been using Unix and Linux for 36 years now; I use find almost daily and find -depth fairly often, but I can't recall an occasion when I wanted to traverse a directory tree breadth-first. It just isn't a common need.

The second reason: breadth-first traversal consumes much more memory.

For depth-first search, memory consumption is $O(\log n)$: all you need to keep in memory is the stack of nodes leading up to the current node.

For breadth-first traversal, it is $O(n)$: you need to keep the whole queue of unvisited nodes in memory, which at some point includes all nodes of a given depth.

For instance, on one of my Linux systems, the root directory contains 1448354 files, its highest directory depth is 25, and the highest number of files and directories at the same depth is 325680 (for depth 7). So a find / on that Linux system will maintain a stack with a maximum size of 25, while a breadth-first traversal of / will maintain a queue with a maximum size of about 325680. Why spend all that memory? We can obtain the same result in a memory-efficient way by running a series of consecutive find commands:

find / -maxdepth 1 [...]
find / -mindepth 2 -maxdepth 2 [...]
find / -mindepth 3 -maxdepth 3 [...]
[...]

There is just no need for find -breadthfirst.

You may always run into a graph traversal use case that really requires breadth-first and nothing else. Those cases are rare, and if your graphs can be large, make sure you have the memory to spare.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.