Prerequisite:
Please study below topics before starting current tutorial.
2. Stack
4. Recursion
5. DFS
Why traversal algorithm is required?
- The purpose of the tree or graph is to organize the collection of data in the graph or tree format based on problem requirement. But to process the data represented in the tree or graph data structure, some mechanism is required. These set of mechanisms are called traversal algorithms and such traversal is required to process data represented by the tree or graph.
Definition:
Inorder traversal is a type of depth-first traversal used in binary trees which starts from root node and process all the nodes of the tree. In inorder traversal, the nodes are recursively visited and processed in the following order:
- Traverse the left subtree in inorder- First go to the left child node if it is present, apply the inorder traversal on the left child node.
- Process data at current node- Once inorder has been applied on left child node, process the data stored in the current node( In starting it is root node).
- Traverse the right subtree in inorder. - Once left subtree has been processed and data at the current node has been processed, go to the right child node and apply inorder traversal on the right child node.
In short we can memorize this algorithm as LEFT->ROOT->RIGHT or in short LRtR formula. It means, first apply inorder on the left subtree of given root/current node then process the data present at root/current node then apply inorder traversal on the right subtree of given root/current node. For reference, in remaining tutorial we will recall this formula in short as LRtR.
Example - How Inorder traversal works :
First we concentrate on the below binary tree to understand the inorder binary tree traversal:
1. Since node 1 is the root node here, processing will start from node 1.
3. Node 2 doesn't have any left subtree so according to LRtR formula data at current node is processed as given below:
4. After processing data at node 2, according to LRtR formula processing of right subtree of node 2 will start as given below:
5. Node 4 has left subtree so according to LRtR formula processing of left subtree of node 4 will start as given below:
6. Since node 6 has no left child so data at node 6 will be processed. Since node 6 is leaf node(no right child node) so first time the whole formula LRtR is processed at node 6. So node 6 is fully processed here and processing backtracks to its immediate partial processed node 4.
7. According to LRtR formula L part has already been processed at node 4 so next Rt part (means data present at node 4) is processed as given below:
8. R part of formula LRtR at node 4 is remaining, so processing of the right subtree of node 4 starts.
9. Since node 7 is leaf node the left subtree of node 7 is implicitly processed as no left child is present. Then the next part, data at node 7 is processed. Finally there is no right child here so the right subtree of node 7 is also implicitly processed and the process backtracks to its immediate partial processed parent node 4.
10. At node 4 whole part of LRtR is processed so node 4 is fully processed and process backtracks to node 2 where node 2 is also fully processed and the process again backtracks to node 1. At node 1 L part of LRtR is processed so next Rt(data at current node) part is processed.
11. According to LRtR formula, processing of the right subtree with root node 3 of node 1 starts.
12. Since node 3 has left subtree, so according to LRtR formula processing of the left subtree of node 3 starts.
13. Node 5 has no left child so its left subtree is implicitly processed then according to LRtR formula data present at node 5 is processed then the processing of its right subtree starts.
14. Since node 8 is leaf node so all part of formula LRtR is applied here and this node is fully processed and control backtracks to node 5. Then node 5 is also fully processed and control backtracks to node 3.
15. At node 3 left subtree is completely processed. Next data at node 3 is processed and since no right child present here its right subtree is implicitly processed and control backtracks to node 1 where the right subtree of node 1 is also processed. Thus full processing of root node of given tree happens leaving complete inorder traversal of given tree as given below:
Output of the the above inorder traversal will be : 2,6,4,7,1,5,8,3
Implementation:
To represent the tree node, below data structure will be used in this tutorial.
Inorder traversal can be implemented by two methods.
Method 1: Using STACK
In inorder traversal it can be easily observed that a node is only processed if LRtR formula is fully applied on the given node. Fully means if node has left subtree then it must be processed, then the same for right subtree. If left subtree has another left or right subtree then those subtrees must be processed. This process will go till the leaf node then backtracking happens from there.
Remember till backtracking a chain of partial processed nodes exist where it is necessary to keep track of order of vertices in which Inorder traversal algorithm has been applied on the partial processed nodes. The first full processing happens on the last node(leaf node) then process returns back to node which is predecessor of the last visited node and so on.
Here we see that a chain of partial processed nodes is created where backtracking happens or the first full processing happens on the last added node in the chain. After that this node is removed from the chain. And the root node is completely removed from the chain at last. If we try to remember such data structure where last added node is processed first and first added node is processed last then such type of data structure is LIFO(Last In First Out) which is STACK data structure. Below figure illustrates the same.
inorderByStack(root)
{
- Let ST is a stack
- let current=root
- While ST is not empty or current is not not null:
- {
-
while current is not null
-
{
-
ST.push(current)
-
current=current.left
-
}
-
current=ST.pop()
-
Process current.data(print current.data)
-
current=current.right
- }
Below is the explanation of the above algorithm:
- In the starting at line no 3 current variable is not null but stack is empty. Since the current is not null it will go to while loop at line no 5 where left node is added to the stack recursively according to LRtR formula where L part is processed first.
- If any node is found where no left child is present, control goes out of while loop at line 5. Here next part of LRtR is processed by popping top item from the stack which is last node in the chain having no left child.
- After processing data at current node according to LRtR formula, right subtree must be processed so current is assigned to right child of current node
- If any node don't have right subtree then current will be null. In that case if stack has entry to process backtrack will happen.
Method 2: Using Recursion
From the above figure we can easily see inorder traversal can be implemented recursively. As we know from Recursion chapter, while designing recursive solution there are 3 steps to follow which are given below:
Hypothesis - In designing recursive solution we should define a function and its necessary parameter which will solve the given problem. In our case while applying inorder traversal to any node we need the left child, node data and the right child node which will be accessed from the given node itself. So only the current node is sufficient input parameter where processing will start from the root node. We are defining below function which will solve our problem.
Inorder(root)
Inductive Step - Here we need to define the problem in terms of the subproblems of itself. Here we know from the above mentioned formula inorder works on formula LRtR(Apply inorder on the left subtree, process the data on current node, apply inorder on the right subtree). So we can define inorder traversal as below in the inductive step.
Inorder(root)=Inorder(root.left)=>(process data at root)==>Inorder(root.right)
or
Inorder(root)=
Inorder(root.left)
(Process data at root)
Inorder(root.right)
Base Condition - Function body defined in the Inductive step will not work as after leaf node left or right child will be null so there must be some condition to handle this boundary which is called Base Condition. Here if current node is null means no subtree to process. So there must not be any processing when current node is null as given below:
Inorder(root)=
if root is null do nothing and return
Inorder(root.left)
(Process data at root)
Inorder(root.right)
So below will be inorder tree traversal algorithm for a given binary tree using recursion
inorderByRecursion(root)
{
{
- If the root node is null then do nothing and return
- Inorder(root.left)
- Process root.data(print root.data)
- Inorder(root.right)
Below is the java code implementation for the above mentioned Inorder tree traversal algorithms
import java.util.Stack;
public class InorderTraversalTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Node n1=new Node(1);
Node n2=new Node(2);
Node n3=new Node(3);
Node n4=new Node(4);
Node n5=new Node(5);
Node n6=new Node(6);
Node n7=new Node(7);
Node n8=new Node(8);
n1.left=n2;
n1.right=n3;
n2.right=n4;
n3.left=n5;
n4.left=n6;
n4.right=n7;
n5.right=n8;
System.out.println("===============Below is Inorder By Stack===============");
InorderTraversal order=new InorderTraversal();
order.inorderByStack(n1);
System.out.println("===============Below is Inorder By Recursion===============");
order.inorderByRecursion(n1);
}
}
class Node
{
int data;
Node left;
Node right;
public Node(int k)
{
data=k;
}
}
class InorderTraversal
{
public void inorderByStack(Node root)
{
Stack<Node> st=new Stack<Node>();
Node current=root;
while(!st.isEmpty()|| current!=null)
{
while(current!=null)
{
st.push(current);
current=current.left;
}
current=st.pop();
System.out.println(current.data);
current=current.right;
}
}
public void inorderByRecursion(Node root)
{
if(root==null)
{
return;
}
inorderByRecursion(root.left);
System.out.println(root.data);
inorderByRecursion(root.right);
}
}