tree traversal. Inorder, preorder, postorder

4
votes

I understand the idea behind the tree traversal as well as implementations, but here is the question. Why do we need them all?

Right now I only know that preorder traversal is used when parsing math expressions. From the Wikipedia I also read than:

  • Inorder traversal is particularly common to use an inorder traversal on a binary search tree because this will return values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name). Preorder traversal
  • Traversing a tree in preorder while inserting the values into a new tree is common way of making a complete copy of a binary search tree. One can also use preorder traversals to get a prefix expression (Polish notation) from expression trees: traverse the expression tree preorderly. (which I already stated)

But these examples are rather vague. Can anyone describe this in more depth. Especially with examples.

2
algorithmtreebinary-tree

2 Answers

6
votes

Consider the problem of doing some file operation on a directory tree. When the operation is removal of files, then you need to empty each directory before removing the directory itself, so you need a post-order traversal. By contrast, when copying the hierarchy, you need to copy the directories first, so then you need a pre-order traversal.

I honestly don't see what's vague about the BST in-order traversal. When you want to display the contents of a BST on-screen in a user interface, you want the keys to show up sorted, don't you? (If you didn't, then using a BST would probably be a bad idea since a hash table is often faster.)

3
votes

I can think of many examples. Performance for example.

Imagine a tree in real life. It has a stem and the stem has 3 branches. Each of those inner branches has 3 outer branches. So it has 9 outer branches.

One of the 3 inner branches is dead and subsequently its 3 outer branches are dead also.

Now you want to cut of all the dead branches. The tree has 13 branches(1 stem 3 inner and 9 outer). Do you have to look at them all individually to determine if you want to cut them or not? No

Now imagine there is a robot that wants to cut of all dead branches. In its software bran it looks at the stem.. is it dead? No. It then looks at the first inner branch is it dead? Yes! Then it will cut of that branch and at the same time its outer branches will be cut off.

Instead of making 13 choices it only has to make 10. (The stem, the 2 healthy inner branches, their 6 outer branches and the sick inner branch)