Tree traversal techniques in DSA

Share

Introduction

Tree traversal means simply visiting every node in a tree exactly once in any specific order and may. Tree traversal is done for certain operations such as displaying the content of nodes, checking for the presence of a certain key in the tree. But we can’t access or visit the tree in any random way as we like.

There are three ways in which tree can be traversed. They are:

  1. In-Order traversal
  2. Pre-order traversal
  3. Post-order Traversal

In-Order Traversal ( Left- Root – Right)

While visiting the tree, it should be noted that every node itself in a tree represents a sub-tree. So, in this traversal method, the left subtree is visited first in In-order. Then the root is visited and lastly, the right subtree is visited in In-order.

Algorithm:

1. Start
2. If root==NULL,
            display "Tree does not exist"
3. Traverse left sub tree in In-order.
4. Visit the root.
5. Traverse right sub tree in In-order.
6. Stop

We first check for the presence of roots by visiting A. Then, for In-order we traverse the left sub-tree B which is visited in In-order. Then we visit the root of the main tree ( i.e. A) and lastly right subtree C is traversed in In-order.

The output for the In-order traversal of the given tree will be:

D-B-H-E-I-A-F-C-G

Pre-Order Traversal ( Root -Left- Right )

In this traversal method, firstly we visit the left subtree in post-order. Then, the right subtree is visited in post-order. Lastly, we visit the root.

Algorithm:

1. Start
2. If root==NULL,
            display "Tree does not exist"
3. Visit the root.
4. Traverse left sub tree in pre-order.
5. Traverse right sub tree in pre-order.
6. Stop

We first check for the presence of roots by visiting A. Then, for pre-order, we visit the main root(i.e. A) itself. Then, we traverse the left sub-tree B in pre-order. Lastly, right subtree C is traversed in pre-order.

The output for the pre-order traversal of the given tree will be:

A-B-D-E-H-I-C-F-G

Post-Order Traversal ( Left- Right- Root )

In this traversal method, left subtree is visited firstly in post-order. Then, right subtree is visited in post-order. Lastly, the root is visited.

Algorithm:

1. Start
2. If root==NULL,
            display "Tree does not exist"
3. Traverse left sub tree in post-order.
4. Traverse right sub tree in post-order.
5. Visit the root.
6. Stop

We first check for the presence of root by visiting A. Then , for post-order , we traverse the left sub-tree B in post-order. Then ,right subtree C is traversed in post-order. Lastly we visit main root(i.e. A) itself.

The output for the post-order traversal of the given tree will be:

D-H-I-E-B-F-G-C-A

Share

Leave a Reply

Your email address will not be published.

%d bloggers like this: