Tree traversal is a process of visiting all the nodes of a tree in a systematic order.
‣ There are three standard methods to traverse the binary trees.
These are as follows:
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
Preorder Traversal:
Preorder traversal is a tree traversal algorithm that visits the root node of a tree first, followed by the nodes in the left subtree in preorder, and then the nodes in the right subtree in preorder.
Steps:
- If root =NULL, return
- Visit the root
- Traverse the left subtree in preorder
- Traverse the right subtree in preorder
Note:
In preorder traversal, the nodes are visited in the following order:
- Current node
- Left subtree
- Right subtree
Java Code implementation of Preorder traversal:
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root = null; }
// Given a binary tree, print its nodes in preorder
void printPreorder(Node node)
{
if (node == null)
return;
// First print data of node
System.out.print(node.key + " ");
// Then recur on left subtree
printPreorder(node.left);
// Now recur on right subtree
printPreorder(node.right);
}
// Driver code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
// Function call
System.out.println(
"Preorder traversal of binary tree is ");
tree.printPreorder(tree.root);
}
}Output:
Preorder traversal of binary tree is
1 2 4 5 3 Inorder Traversal:
Inorder traversal is a tree traversal algorithm that visits the nodes in the left subtree of a tree in inorder, followed by the root node, and then the nodes in the right subtree in inorder.
Steps:
- If root=NULL, retrurn
- Traverse the left subtree in inorder
- Visit the root
- Traverse the right subtree in inorder
Note:
In inorder traversal, the nodes are visited in the following order:
- Left subtree
- Current node
- Right subtree
Java Code implementation of Inorder traversal:
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root = null; }
// Given a binary tree, print its nodes in inorder
void printInorder(Node node)
{
if (node == null)
return;
// First recur on left child
printInorder(node.left);
// Then print the data of node
System.out.print(node.key + " ");
// Now recur on right child
printInorder(node.right);
}
// Driver code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
// Function call
System.out.println(
"Inorder traversal of binary tree is ");
tree.printInorder(tree.root);
}
}Output:
Inorder traversal of binary tree is
4 2 5 1 3 Postorder Traversal:
Postorder traversal is a tree traversal algorithm that visits the nodes in the left subtree of a tree in postorder, followed by the nodes in the right subtree in postorder, and then the root node.
Steps:
- If root=NULL, return
- Traverse the left subtree in postorder
- Traverse the right subtree in postorder
- Visit the root
In postorder traversal, the nodes are visited in the following order:
- Left subtree
- Right subtree
- Current node
Java code implementation for postorder traversal:
class Node {
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BinaryTree {
// Root of Binary Tree
Node root;
BinaryTree() { root = null; }
// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(Node node)
{
if (node == null)
return;
// First recur on left subtree
printPostorder(node.left);
// Then recur on right subtree
printPostorder(node.right);
// Now deal with the node
System.out.print(node.key + " ");
}
// Driver code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
// Function call
System.out.println(
"Postorder traversal of binary tree is ");
tree.printPostorder(tree.root);
}
}Output:
Postorder traversal of binary tree is
4 5 2 3 1 Traversal Techniques:
