Tree Traversal in Data Structure

Tree traversal in data structure is an important topic from exam point of view.
There are three techniques of traversing a tree in Data Structure.
These tree traversing techniques in Data Structure are in order traversing, pre order traversing and post order traversing techniques.

Sometime questions based on tree traversal in data structure examples are also asked in GATE(CS) and UGC NET Exam.

So tree traversal in data structure topic is also important for GATE and UGC exam point of view.

In this tutorial we have discussed tree traversal methods in Data Structure.

First we will understand basics of Tree.

What is Tree in Data Structure ?

Tree is not a Linear Data Structure like array or linked list.
A Linear Data Structure starts with a logical start and logical end.
But in a tree when we point to a specific node, we can point to more than 1 possible direction or more than 1 possible next node.

In the Binary Tree above, if we start with the root node, we can either go to node D or to node J.

If we visit one direction, we have to go back to the root and then visit the other direction later.

So tree traversals are not as straight forward as arrays or Linked Lists.

Tree traversal can be defined as visiting each node in the tree exactly once following same order.
Visiting a node means reading or processing the data in the node.

Based on the order of visiting nodes in a tree, tree traversal algorithms can be broadly classified into two categories.

There are three methods or three possible permutations of tree traversal in data structure including pre order traversing.

1.Pre order traversal.

2. In order traversal.

3.Post order traversal.

Detailed description of these tree traversal techniques in data structure are as follow-

Algorithm for Pre Order Tree Traversal has the following steps.

Students should keep in mind the <root><left><right> rule for pre order tree traversal.

In the above tree, for pre order traversal we’ll first read the data in the root node, i.e. F.
Then, we’ll move to the left sub tree. Here we see the root of left sub tree is D.
Then we’ll again move to the left sub tree where the root is B.
Then we’ll move to the left child of B i.e. A.
Then we’ll visit the right child of B i.e. C. It’ll go on like this.
Once left sub tree is done, we’ll move to the right sub tree and visit the nodes accordingly.

Hence the Pre Order Traversal of the above tree would be as follow

Here the order of traversal is <left><root><right>. i.e.
First we’ll visit the left sub tree, then read the data in the root node and then finally visit the right sub tree.
In the tree below, we’ll first visit the left sub tree of the root node F.
In the left sub tree the root node is D. We’ll again go to the left of D, we’ve got B.
Again to the left of B we’ve got A.
As there’s nothing on the left of A, we read the data on A and then move to the root node B and then to the right of B, i.e. C. It’ll go on like this.

The In Order Traversal of the above tree would be .

Here the order of traversal is <left><right><root>.
First visit the left sub tree, then the right sub tree and finally read the data on the root node.
In the above tree, we’ll first visit the left sub tree of the root node F first and then we’ll visit the right sub tree of the root node and finally read the data on the root node; i.e. F.

The Post Order Traversal in this case would be

Some problems based on Tree Traversal methods in Data Structure are given here with solutions.

Here in this tree traversal tutorial we have discussed the tree traversal in data structure.
Three tree traversing techniques in order traversal , post order traversal and pre order traversal are explained here in this post.

I hope after reading this tutorial students will be able to learn solve the problems based on tree traversal.

If you have any query or problem regarding tree traversal algorithm then feel free to ask in comment section.