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:
Preorder traversal is a type of depth-first traversal used in binary trees which starts from root node and process the all nodes of the tree. In preorder traversal, the nodes are recursively visited and processed in the following order:
- Visit and process the data stored in the current node( In starting it is root node).
- Traverse the left subtree in preorder- After processing the data at the current node go to the left child node if it is present, apply the preorder traversal on the left child node.
- Traverse the right subtree in preorder. - Once data at the current node and whole left subtree of current node is processed go to the right node and apply preorder traversal on the right node.
In short we can memorize this algorithm as ROOT->LEFT->RIGHT or in short RLR formula. It means, first process data present at root/current node then process left subtree of given root/current node then right subtree of given root/current node. For reference, in remaining tutorial we will recall this formula in short as RLR.
Example - How Preorder traversal works :
First we concentrate on the below binary tree to understand the preorder binary tree traversal:
1. Here node 1 is the root node, so traversal will start from node 1. According to ROOT->LEFT->RIGHT formula data at node 1 will be processed first and then preorder will be applied on the left subtree of node 1 which is subtree started with node 2 which is represented in the below figure.
2. Next data at node 2 will be processed and there is no left child for node 2, so according to RLR formula preorder will be applied on right subtree which is subtree with root node 4.
3. Next data at node 4 will be processed and its left subtree with root node 6 will be processed.
4. Next data at node 6 will be processed and since node 6 is leaf node(no left and right child) processing will backtrack to its immediate parent node which is node 4 by marking node 6 as processed . Here according to RLR formula RL part has been processed but last R part is remaining, so preorder will be applied on the right subtree of node 4 which is subtree started with node 7.
6. According to above mentioned steps all remaining nodes will be processed as given in the below figures.
Implementation:
To represent the tree node, below data structure will be used in this tutorial.
Preorder traversal can be implemented by two methods.
Method 1: Using STACK
In preorder traversal it can be easily observed that a node is only processed if RLR 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 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 Preorder 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.
Below is the algorithm to implement preorder tree traversal using STACK.
preorderByStack(root)
{
- Let ST is a stack
- ST.Push(root)
- While ST is not empty:
- {
-
item=ST.pop()
-
Process item.data(print item.data)
-
If item.right is not null then ST.Push(item.right)
-
If item.left is not null then ST.Push(item.left)
- }
In the above algorithm the right child is pushed first. It is because in stack item pushed first is processed at last.
Method 2: Using Recursion
From the above figure we can easily see preorder 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 preorder traversal to any node we need the node data, its left child and right child node which will be accessed from given node itself. So only current node is sufficient input parameter where processing will start from root node. We are defining below function which will solve our problem.
Preorder(root)
Inductive Step - Here we need to define the problem in terms of subproblems of itself. Here we know from the above mentioned formula preorder works on formula RLR(process data at root, apply preorder on left subtree, apply preorder on right subtree). So we can define preorder traversal as below in inductive step.
Preorder(root)=(process data at root)=>Preorder(root.left)=>Preorder(root.right)
or
Preorder(root)=
(Process data at root)
Preorder(root.left)
Preorder(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:
Preorder(root)=
if root is null do nothing and return
(Process data at root)
Preorder(root.left)
Preorder(root.right)
So below will be preorder tree traversal algorithm for a given binary tree using recursion
preorderByRecursion(root)
{
{
- If root is null then do nothing and return
- Process root.data(print root.data)
- Preorder(root.left)
- Preorder(root.right)
Below is the java code implementation for the above mentioned Preorder tree traversal algorithms
import java.util.Stack;
public class PreorderTraversalTest {
/**
* @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 Preorder By Stack===============");
PreorderTraversal order=new PreorderTraversal();
order.preorderByStack(n1);
System.out.println("===============Below is Preorder By Recursion===============");
order.preorderByRecursion(n1);
}
}
class Node
{
int data;
Node left;
Node right;
public Node(int k)
{
data=k;
}
}
class PreorderTraversal
{
public void preorderByStack(Node root)
{
Stack<Node> st=new Stack<Node>();
st.push(root);
while(!st.isEmpty())
{
Node item=st.pop();
System.out.println(item.data);
if(item.right!=null)
st.push(item.right);
if(item.left!=null)
st.push(item.left);
}
}
public void preorderByRecursion(Node root)
{
if(root==null)
{
return;
}
System.out.println(root.data);
preorderByRecursion(root.left);
preorderByRecursion(root.right);
}
}