Tree traversals

WHY TRAVERSAL?

In order to process trees, we need a mechanism for traversing them, and that forms the subject of this section. The process of visiting all nodes of a tree is called tree traversal. Each node is processed only once but it may be visited more than once. As we have already seen in linear data structures (like linked lists, stacks, queues, etc.), the elements are visited in sequential order. But, in tree structures, there are many different ways.

Tree traversal is like searching the tree, except that in traversal the goal is to move through the tree in a particular order. In addition, all nodes are processed in the traversal but searching stops when the required node is found.

TRAVERSAL POSSIBILITIES

Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps are: performing an action on the current node (referred to as “visiting” the node and denoted with “D”), traversing to the left child node (denoted with “L”), and traversing to the right child node (denoted with “R”). This process can be easily described through recursion. Based on the above definition there are 6 possibilities:

1. LDR: Process left subtree, process the current node data and then process right subtree

2. LRD: Process left subtree, process right subtree and then process the current node data

3. DLR: Process the current node data, the process left subtree and then process right subtree

4. DRL: Process the current node data, process right subtree and then process left subtree

5. RDL: Process right subtree, process the current node data and then process left subtree

6. RLD: Process right subtree, the process left subtree and then process the current node data

BINARY TREE TRAVERSAL TECHNIQUES:

Tree traversal is a method of visiting every node in the tree. By visit, we mean that some type of operation is performed. For example, you may wish to print the contents of the nodes.

There are four common ways to traverse a binary tree:

1. Preorder

2. Inorder

3. Postorder

4. Level order

In the first three traversal methods, the left subtree of a node is traversed before the right subtree. The difference among them comes from the difference in the time at which a root node is visited.

INORDER TRAVERSAL:

In the case of inorder traversal, the root of each subtree is visited after its left subtree has been traversed but before the traversal of its right subtree begins. The steps for traversing a binary tree in inorder traversal are:

1. Visit the left subtree, using inorder.

2. Visit the root.

3. Visit the right subtree, using inorder.

The algorithm for inorder traversal is as follows:

void in_order(node *root)

{

if(root != NULL)

{

inorder(root->lchild);

print root -> data;

inorder(root->rchild);

}

}

PREORDER TRAVERSAL:

In a preorder traversal, each root node is visited before its left and right subtrees are traversed. Preorder search is also called backtracking. The steps for traversing a binary tree in preorder traversal are:

1. Visit the root.

2. Visit the left subtree, using preorder.

3. Visit the right subtree, using preorder.

The algorithm for preorder traversal is as follows:

void preorder(node *root)

{

if( root != NULL )

{

print root -> data;

preorder (root -> child);

preorder (root -> child);

}

}

POST ORDER TRAVERSAL:

In a postorder traversal, each root is visited after its left and right subtrees have been traversed. The steps for traversing a binary tree in postorder traversal are: 

1. Visit the left subtree, using postorder.

2. Visit the right subtree, using postorder

3. Visit the root.

The algorithm for postorder traversal is as follows:

void postorder(node *root)

{

if( root != NULL )

{

postorder (root -> child);

postorder (root -> child);

print (root -> data);

}

}

LEVEL ORDER TRAVERSAL: 

In a level order traversal, the nodes are visited level by level starting from the root and going from left to right. The level order traversal requires a queue data structure. So, it is not possible to develop a recursive procedure to traverse the binary tree in level order. This is nothing but a breadth-first search technique.

The algorithm for level order traversal is as follows:

void level_order()

{

int j;

for(j = 0; j < ctr; j++)

{

if(tree[j] != NULL)

print tree[j] -> data;

}

}

EXAMPLES:

1.

•  Preorder traversal yields:  A, B, D, C, E, G, F, H, I
•  Postorder traversal yields: D, B, G, E, H, I, F, C, A
•  Inorder traversal yields: D, B, A, E, G, C, H, F, I
•  Level order traversal yields: A, B, C, D, E, F, G, H, I

2.

•  Preorder traversal yields: P, F, B, H, G, S, R, Y, T, W, Z
•  Postorder traversal yields: B, G, H, F, R, W, T, Z, Y, S, P
•  Inorder traversal yields: B, F, G, H, P, R, S, T, W, Y, Z
•  Level order traversal yields: P, F, S, B, H, R, Y, G, T, Z, W