Page 223 - DCAP407_DATA_STRUCTURE

Data Structure

Step 3: Pop the top of the stack.
Repeat while the pointer value is not NULL.
Write (Node containing data).
If the right sub-tree is not empty, then stack the pointer to the right sub-tree and set pointer value to left
sub-tree.
12.3 Inorder Traversal

The inorder traversal of a non-empty tree is defined as follows:
1. First, traverse the left sub-tree of the root node in inorder.
2. Next, visit the root node.
3. Finally, traverse the right sub-tree of the root node.
The figure 12.3 depicts the functioning of inorder traversal. The figure provides a functional procedure
of the inorder traversal.

Figure 12.3 Inorder Traversal

The algorithm for inorder traversal is as follows:

1. Input – ROOT is the pointer to the root node of binary tree
2. Output – Visiting all nodes in inorder manner
3. Data Structure – Linked structure of binary tree
Steps:
Inorder(Node *ptr)
1. ptr = ROOT //Start from ROOT
2. If (ptr ≠ null) then //If it is non-empty node

3. Inorder (ptrllink) //Traverse left sub-tree of node in inorder
manner
4. Visit (ptr) //Visit the node
5. Inorder (ptrrlink) //Traverse right sub-tree of node in inorder
manner
6. EndIf
7. Stop

216 LOVELY PROFESSIONAL UNIVERSITY