Applications of Traversals

 

Author Note

  Instead of just studying about traversals, thought of writing about various applications of traversals. So that, we can slowly move into self-balancing search trees. But, in-between will bring in some Stack/Queue and Interview Problems to break the monotonous mode of the blog. :) That gives more fun as well!!

See Also

http://analgorithmaday.blogspot.com/2011/05/construct-binary-tree-from-pre-order.html

Introduction

  Unlike normal array/linked list data structures where we traverse linearly, in a tree we have different combinations of traversals possible. Without knowing these clearly, we cannot use trees effectively. As we already know more about trees & traversals, we will see the example based introduction to where it is used.

   Pre-order traversal

      As we already know. root-left-right. If from in-order traversal, we can extract the sorted values in a BST. Similarly There are many things we can derive from pre-order as well. Many operations which needs to visit all the root nodes first use pre-order traversals.

We will see some of the following applications now,

• Tree copying
• Counting the number of nodes
• Counting the number of leaves
• Prefix notation from a expression tree

   Post-order traversal

     Post order first finishes the left-right and then visits the root. Its similar to popping elements from a tree. You take the leaves first and then the root.

  The common applications are

• Deleting a binary tree
• All stack oriented programming languages – mostly functional languages which fully works on nested functions.
• Calculator programs
• postfix notation in an expression tree – used in calculators

More concepts

   More than just traversal, there are other necessary things we need to learn clearly from these traversals.

• in-order successor/predecessor
• pre-order successor/predecessor

post-order is not having any common applications as such. But we will still see that as well

Here are some image snapshots from http://www2.hawaii.edu/~sugihara/course/ics311f08/notes/ThreadedTrees.html#S2

 

In-order successor/predecessor

1. Find the in order successor of v ? s is the in-order successor

 

2. Find the in order predecessor of v ?

 

Preorder successor and predecessor

1. Find the pre-order successor of v?

  If a left node is there, then,

If there is no left node, then,

If there is no child for v, then,

There is a concept called Threaded trees which we will see in the next articles. It’s very useful in cases where you don’t have a parent attribute part of the node.

If you have a parent link then, you have to just identify the parent of v who has a right child. This is simply because, a node without left or right ends the recursion at either left or right. So, it needs to go to the parent and check the right which is the successor. Note that, if we are ending at the right recursion, we need to go to a parent where we have a right node which is not visited.

We will see code for all these in coming articles.